[PYTHON] Optimisation des combinaisons linéaires (calendrier)

objective optimization Abstract J'ai essayé le problème d'optimisation de la combinaison d'allocation de tâches horaires en utilisant python et pulp. Code référencé [^ pakuri_moto]

Motivation Supposons que vous receviez l'e-mail suivant.

M. ○○ ... Pour l'événement de demain, $ I $ personnes postulent pour l'entreprise $ J $. Puisqu'il est $ T $ par personne ($ I <J $), je pense qu'il y aura du temps libre dans l'allocation. ...

J'y ai réfléchi un moment, mais cela semble intéressant en tant que problème général. Quand je le mets sur l'épaule du géant, il semble qu'il y ait un problème d'optimisation des combinaisons. Alors, considérons un problème d'optimisation de combinaison tridimensionnelle (linéaire) qui place $ J $ sur le plan $ I, T $ [^ footnote1]. La version 2D est dans [^ pakuri_moto], alors considérons la version 3D basée sur cela. Le fait est qu'il suffit d'augmenter la variable d'un. Mettez le code complet sur github [^ github], et n'expliquez que les points importants.

Model Un problème d'optimisation de combinaison linéaire en trois dimensions avec $ c_ {ijk} $ comme coût

\begin{align}
Min\left(\sum_{i\in I}\sum_{j\in J}\sum_{t\in T} c_{ijt}x_{ijt}\right)
\end{align}

Ici, $ I $ est une personne, $ J $ est une entreprise et $ T $ est une heure ($ I> J $ est supposé dans l'histoire, mais ce n'est pas nécessaire). $ x_ {ijt} $ est une variable qui prend $ 0 $ ou $ 1 $. $ 0 $ ne correspondra pas, $ 1 $ correspondra. Puisqu'il s'agit d'un horaire cohérent, nous supposons qu'il est indépendant du temps (aucun fuseau horaire n'est gênant les uns pour les autres). Autrement dit, $ c_ {ijt} $ ne dépend pas de $ t $ [^ footnote2]. Je me sens comme $ c_ {ijt} $, mais je veux le minimiser, donc si $ c_ {ijk} $ est négatif, il sera plus facile de faire correspondre $ I $ et $ J $, et si $ c_ {ijk} $ est positif, Ce sera difficile à égaler. Si l'entreprise nomme une personne par loterie, tous les $ c_ {ijk} $ à combiner doivent être de la même constante. Alternativement, il peut être intéressant pour les rassemblements de haut niveau d'avoir un système de points dans lequel les entreprises accordent la priorité à la priorité qu'elles souhaitent parler aux gens. La mise en œuvre est la suivante [^ footnote_iter].

x = {}
for i in I:
    for j in J:
        for t in T:
            x[i, j, t] = pulp.LpVariable("x({:},{:},{:})".format(i,j,t), 0, 1, pulp.LpInteger)

problem += sum(c[i,j,t] * x[i,j,t] for i in I for j in J for t in T)

Ajoutons une contrainte à cela.

Je pense qu'il peut être malheureux pour l'autre de frapper une entreprise plusieurs fois par jour.
Les humains ne peuvent pas être séparés, ils ne peuvent donc pas correspondre à plusieurs entreprises en même temps.
Les entreprises ne peuvent pas être séparées, elles ne correspondent donc pas à plus d'une personne à la fois [^ footnote3].
C'est triste s'il y a trop de biais selon la personne, alors frappons l'entreprise avec la valeur attendue [^ footnote_expec]. La mise en œuvre est la suivante.

for i in I:
  for j in J:
    problem += sum(x[i,j,t] for t in T) <= 1

for t in T:
  for i in I:
    problem += sum(x[i,j,t] for j in J) <= 1

for t in T:
  for j in J:
    problem += sum(x[i,j,t] for i in I) <= 1

for i in I:
  problem += sum(x[i,j,t] for j in J for t in T) >= min(int(expec), len(J))

Je vais faire ce qui précède

solver = pulp.solvers.PULP_CBC_CMD()

résultat

Par exemple, considérons le cas de $ I = (P1, .., P9), J = (C1, ..., C6), T = (T1, ..., T7) $. La fonction de coût a été convenablement décidée comme suit. Comme il est défini pour $ (I, J) $ et dit que cela ne dépend pas du temps, il n'y a pas de délai. Il vaut mieux le faire que de ne pas correspondre, donc quand il correspond, il est infiniment petit (ici, $ (ici, $ (ici) -1) Je vous fais un profit de $) [^ footnote4].

cc = np.array([
      [-1,  -1,  -1,  -11, -11, -11],
      [-1,  -1,  -11, -1,  -11, -11],
      [-1,  -1,  -11, -11, -1,  -11],
      [-1,  -1,  -11, -11, -11, -11],
      [-1,  -1,  -11, -11, -11, -1],
      [-1,  -11, -11, -11, -11, -1],
      [-11, -11, -1,  -11, -11, -1],
      [-11, -11, -11, -1,  -11, -1],
      [-11, -11, -11, -11, -1,  -1],
     ])

À ce moment, il se termine immédiatement et les résultats suivants sont obtenus. Je pense que c'est probablement là.

Conclusion J'ai essayé un problème d'optimisation de combinaison 3D. Au départ, nous avons supposé $ J <I <T $, mais le code dans son ensemble concernera tous les cas. Pour être honnête, il n'y a pas de résultats particulièrement intéressants, mais je pense qu'il serait intéressant que les effets non linéaires suivants puissent être incorporés dans la fonction objectif.

Je vais donner aux gens du temps libre. $ \ Sum_ {j} x_ {i, j, t} \ sum_ {j} x_ {i, j, t \ pm1} $
Éliminez un peu plus fermement l'injustice $ (\ sum_ {j, t} x_ {i, j, t} - \ sum_ {j, t} x_ {i ', j, t}) ^ {2} $. Cela peut-il être implémenté comme linéaire?
Je veux discuter avec d'autres personnes pendant mon temps libre, mais il vaut mieux ne pas discuter avec la même personne Peut-être. $ \ Sum_ {j, t} x_ {i, j, t} \ sum_ {j, t} x_ {i ', j, t} (i \ neq i') $ Je vous serais reconnaissant de bien vouloir me faire savoir si vous avez un malentendu mortel dû à la mise en œuvre d'une contrainte, etc.

references

[^ footnote1]: En plus du travail, il y a probablement diverses applications telles que des arrangements de conversation et des horaires d'activités de mariage (en fait, il y avait des arrangements de conversation [^ pycon16], [^ pycon18].).