[Recherche opérationnelle] Sortie de Gurobi 7.0

Avec d'intéressants gains de performance et des facilités pour l'optimisation multiobjectif

Du côté de la recherche opérationnelle, rare sont les solveurs commerciaux dont la performance est au sommet. Les derniers tests de Hans Mittelman en montrent trois pour les problèmes linéaires en nombres entiers (MILP) : CPLEX, Gurobi et Xpress MP. Gurobi voit apparaître une nouvelle version majeure, numérotée 7.0, deux ans après la précédente. Celle-ci apporte des gains de performance intéressants pour une grande série de modèles, selon les tests effectués par l’éditeur : de 19 % pour des problèmes entiers linéaires (MIP) à 164 % pour les problèmes à contraintes quadratiques et à objectif quadratique complexes (qui prenaient plus de cent secondes de résolution pour la version précédente). Difficile d’extrapoler ces résultats pour des problèmes précis, mais la grande majorité des utilisateurs devrait voir un impact très positif en termes de performance. Il faut cependant remarquer que ces gains en performance sont plus modestes que pour bon nombre de versions précédentes du solveur.

Au niveau des fonctionnalités du solveur, il est possible depuis longtemps, pour les problèmes avec des variables entières (qui doivent donc être résolus par l’algorithme de séparation et évaluation), de récupérer plusieurs solutions réalisables : l’utilisateur peut maintenant spécifier, avant la résolution, le nombre de telles solutions qu’il souhaite récupérer, ainsi que leur qualité (écart maximum de l’objectif par rapport à la solution optimale).

Le sujet est souvent abordé : Gurobi propose maintenant des fonctionnalités pour l’optimisation multiobjectif. Quand l’utilisateur donne plusieurs fonctions objectif, il peut demander au solveur d’optimiser une pondération de ces différents objectifs ou de les traiter de manière hiérarchique (par exemple, optimiser pour le coût ; ensuite, en gardant le même coût ou en autorisant une certaine déviation, optimiser pour les impacts environnementaux)… ou encore une combinaison des deux.

Tout comme la version 6.0, l’interface de modélisation de Gurobi s’étend à de nouvelles fonctions : il devient possible d’insérer automatiquement des minimums, des maximums, des valeurs absolues, des expressions booléennes (uniquement pour les opérandes ET et OU), des conditions (indicatrices) dans les contraintes d’un problème. Par derrière, le solveur trouve une formulation linéaire pour ces contraintes, de manière automatique — ce qui facilite un peu le travail de modélisation.

Les améliorations algorithmiques qui soutiennent ces nouvelles fonctionnalités ne sont pas encore décrites, mais quelques éléments devraient parvenir lors de la présentation de Gurobi 7.0 à la conférence INFORMS. La documentation parle d’ores et déjà de nouvelles techniques de génération d’inégalités valides (avec les paramètres InfProofCuts et StrongCGCuts).

Source : site Web de Gurobi.