le nombre maximum de BoolVar avant ou-tools n'est plus possible à utiliser

Aug 18 2020

Le problème d'ordonnancement infirmier standard qui est utilisé comme exemple pour OR-Tools (voir par exemple https://developers.google.com/optimization/scheduling/employee_scheduling) tente d'attribuer des valeurs booléennes aux variables booléennes dans la ligne de code suivante:

shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))

Pour ce problème de jouet, OR-Tools fonctionne bien, mais seulement 105 variables booléennes sont créées (5 infirmières, 7 jours, 3 équipes $\Rightarrow 3\times 5\times7=105$ booléens à attribuer à savoir si une infirmière donnée travaille un quart de travail donné).

J'explore l'utilisation des OU-Tools pour résoudre un problème de planification plus réaliste dans le monde réel. Pour le problème du monde réel auquel je suis confronté, les quarts de travail sont attribués par incréments de 15 minutes et il y a plus de travailleurs et plus de rôles impliqués. Au final, je me retrouve avec 11 064 booléens à attribuer.

Est-ce trop pour s'attendre à ce que OR-Tools fonctionne de manière réaliste? Je trouve qu'il produit rapidement un programme (pas très bon), mais même si je le laisse fonctionner pendant une heure, il ne s'améliore pas du tout par rapport au calendrier initial qu'il a établi dans les premières secondes.

Est-ce un comportement typique pour OR-Tools? Des pensées?

Réponses

4 LaurentPerron Aug 18 2020 at 19:33

Il n'y a pas de bonnes réponses à cette question. Cela dépend du modèle, de la complexité du problème. Ma réaction instinctive est que OR-Tools résout régulièrement à l'optimalité des problèmes plus importants, mais certains problèmes beaucoup plus petits peuvent être impossibles à prouver, ou même à trouver une solution réalisable.

OR-Tools est un bon solveur de CP (il a remporté les 4 médailles d'or des 2 derniers défis minizinc). C'est également un solveur MIP décent (il a fermé 5 instances MIPLIB 2017 ouvertes et amélioré les limites sur quelques autres).

Je suggérerais ou répéterais les suggestions ci-dessus:

  • comparez à un solveur MIP commercial (Gurobi, Cplex, Xpress) et tentez votre chance.
  • comparer à CPLEX CP-Optimizer. Je ne m'attendrais pas à ce que ce soit mieux après les discussions que j'ai eues avec des chercheurs universitaires qui ont fait la comparaison, mais cela pourrait être un problème lorsque CPO fonctionne parfaitement.
  • envoyez votre modèle à la liste de diffusion des utilisateurs or-tools et demandez de l'aide ou des commentaires, notamment autour des paramètres de recherche.