Sortie de Gurobi 8.0

En ce mois de mai, Gurobi annonce sa version 8.0, après dix ans de développement. Ce solveur d’optimisation mathématique est utilisé dans bon nombre d’industries pour les aider à poser de meilleures décisions à l’aide d’analyse prescriptive : une fois les données accumulées et analysées sur le fonctionnement de l’entreprise (analyse descriptive), comment l’améliorer en pratique ? C’est tout l’objectif des modèles d’optimisation mathématique.

Gurobi 8.0 continue de repousser les limites du possible, avec une performance améliorée et un fonctionnement distant (sur des machines de calcul privées ou infonuagiques) revu. Côté performance et temps de calcul, les améliorations sont comparables aux versions précédentes, notamment pour les modèles linéaires à variables entières  : une quinzaine de pour cent d’amélioration globalement, vingt-cinq sur les instances les plus difficiles (plus de cent secondes de résolution). Ces progrès sont en partis dus à l’implémentation du simplexe dual, en moyenne douze pour cent plus rapide — alors que les gains dans ce domaine sont extrêmement difficiles à obtenir, de par toute la recherche déjà effectuée.

Les interfaces pour MATLAB et R sont maintenant complètes : quelques fonctionnalités comme l’optimisation multiobjectif, les ensembles de solution ou encore les contraintes génériques n’étaient pas disponibles dans ces langages. La boîte à outils d’optimisation de MATLAB 2017b a aussi introduit une nouvelle manière de modéliser les problèmes d’optimisation, très similaire à celle que l’on retrouve partout ailleurs : au lieu de préciser le problème à l’aide de matrices, on peut maintenant générer des variables d’optimisation comme des objets, combiner ces objets pour faire des objectifs ou des contraintes. Gurobi est entièrement compatible avec cette API et peut être appelé avec la méthode solve(). Pour .NET, Gurobi 8.0 est compatible avec .NET Core 2.0, que ce soit sous Windows, Linux ou macOS.

L’utilisateur peut aussi apporter plus d’information au solveur. Par exemple, l’heuristique d’amélioration locale (RINS) est la plus efficace de toutes celles implémentées dans Gurobi, mais fonctionnait jusqu’à présent sans apport extérieur : l’idée est d’imposer les valeurs d’une série de variables entières, puis de continuer à optimiser afin d’obtenir une meilleure solution pour les autres variables (mais bien plus vite, vu qu’il faut considérer moins de variables). Évidemment, la difficulté est de trouver des ensembles de variables pour lesquels ces sous-problèmes ont du sens et aident la résolution du problème global. Maintenant, l’utilisateur peut indiquer des sous-problèmes lui-même : par exemple, toutes les décisions sur un pas de temps, une machine, une région, etc., en fonction de la structure de son problème. De même, Gurobi 8.0 accepte plusieurs solutions de départ partielles pour accélérer sa recherche (le solveur tente de compléter ces solutions pour obtenir une bonne solution de départ et trouver de meilleures bornes).

Pour le calcul distant, la communication entre les clients et les services distants peut maintenant se faire avec HTTP ou HTTPS, des protocoles plus habituels qui devraient faciliter les déploiements et la robustesse — ainsi que la sécurité, avec HTTPS. Des serveurs peuvent être ajoutés de manière dynamique à une grappe de calcul. De nouveaux outils et API REST ont été ajoutés pour suivre de près ses serveurs, leur état, les tâches qu’ils ont traitées.

Sources : communiqué de presse, séminaire en ligne, diaporama.

Advertisements

Sortie de CPLEX 12.8

L’optimisation mathématique sert dans de nombreuses applications pratiques, que ce soit la planification de la production d’électricité ou des horaires dans une compagnie aérienne. Pour résoudre ces problèmes d’optimisation, certaines sociétés comme IBM, Gurobi ou MOSEK développent des solveurs extrêmement performants. Un an après la version 12.7, voici qu’IBM annonce la version 12.8 de son solveur CPLEX.

Cette nouvelle version apporte principalement une refactorisation du système de fonctions de rappel, un système maintenant dénommé “générique”. Ces fonctions sont très utiles pour paramétrer finement le fonctionnement du solveur. Cependant, CPLEX n’était pas pensé pour elles dès le début et désactivait certaines fonctionnalités très intéressantes pour la performance quand elles étaient utilisées : la recherche dynamique, la parallélisation, principalement. La nouvelle approche se débarrasse de ces quelques limitations en apportant une nouvelle API (la précédente reste disponible pour le moment).

Cependant, le nouveau système n’est pas aussi flexible que le précédent. Notamment, pour le moment, il est impossible de contrôler le branchement ou la sélection des nœuds à explorer dans l’arbre de séparation et évaluation. Également, il n’est plus possible de fournir de nouvelles solutions dans un nœud. Ces choix ont été faits selon les statistiques d’utilisation des fonctionnalités, ces trois-là étant les moins utilisées.

L’approche moderne impose également une nouvelle contrainte sur les fonctions de rappel que l’on peut écrire : elles doivent gérer le parallélisme. En effet, toute fonction pourrait être appelée depuis plusieurs fils d’exécution, ce qui pose problème en cas d’accès à des ressources partagées (comme un sous-problème).

Comme chaque version, CPLEX 12.8 apporte quelques améliorations de performance. Quelques chiffres sont donnés : les problèmes qui prenaient plus de cent secondes sur la version 12.7 prennent maintenant, en moyenne, 20 % de temps en moins. Cependant, comme le montre le graphique ci-dessus, l’écart se creuse par rapport à Gurobi : l’an dernier, la différence entre les deux solveurs n’était que d’un point de pourcentage ; maintenant, cet écart se creuse et atteint quatre points.

CPLEX est aussi doté d’un moteur de programmation par contraintes. Celui-ci fait relativement peu parler de lui depuis quelque temps. Avec la version 12.8, sur la suite de tests interne d’IBM, ses temps de résolution (pour prouver l’optimalité d’une solution) ont été divisés en moyenne par deux — une belle prouesse ! Aussi, le solveur donne maintenant explicitement une borne sur la valeur optimale attendue (inférieure pour une minimisation, supérieure pour une maximisation) : elle était précédemment calculée, elle est maintenant publique.

L’API a aussi été quelque peu changée, surtout du côté C++. L’objectif était de mieux séparer les services disponibles en dehors de tout processus de recherche (comme changer des paramètres ou récupérer une solution) de ceux qui en dépendent (propagateurs, évaluateurs, etc.).

Sources : What’s new in CPLEX Optimization Studio 12.8, CPLEX 12.8: Generic Callbacks.

Voir aussi : une présentation de CPLEX 12.8, une présentation du nouveau système de fonctions de rappel.

Premières préversions pour MOSEK 8.1

Le solveur commercial de référence pour les problèmes d’optimisation convexes poursuit son petit bonhomme de chemin : quelques mois après la version 8.0, la première préversion de la 8.1 est disponible. Les améliorations du côté des algorithmes d’optimisation se sont portées sur le solveur conique, plus particulièrement pour les problèmes avec des contraintes très denses (faisant intervenir un grand nombre de variables).

Côté modélisation, l’API Fusion en C++ est désormais disponible pour Windows (uniquement en 64 bits pour le moment avec Visual C++ 2015) ; la bibliothèque ne peut être compilée que de manière statique. Côté Python, la performance a été largement améliorée. De même, la documentation a été retravaillée pour être plus claire, notamment au niveau des API fournies et de l’installation.

Des chiffres officiels d’amélioration de performance des solveurs ne sont pas encore disponibles, ils devraient arriver avec la version finale de MOSEK 8.1, vers la fin septembre.

Sources : notes de version, page de téléchargement.

Sortie de CPLEX 12.7

CPLEX est l’un des plus vieux solveurs d’optimisation à ce jour… et parmi les plus performants. Malgré son héritage (il est commercialisé depuis 1988 !), la nouvelle version, numérotée 12.7 et disponible depuis le 11 novembre, apporte de nouvelles améliorations de performance (tout comme les concurrents Gurobi et MOSEK, c’est habituel), mais ce n’est pas tout : outre des facilités de modélisation (comme Gurobi), CPLEX 12.7 permet d’effectuer une décomposition de Benders de manière (semi-)automatique.

Performance

Les améliorations de performance principales se situent au niveau des MILP — problèmes linéaires en nombres entiers — (voir figure) : 7 % au niveau de la résolution du LP, 15 % pour des MILP compliqués. Les MIQP (problèmes quadratiques en nombres entiers) voient eux aussi une amélioration de l’ordre de 15 % pour les problèmes les plus difficiles, tandis que les MIQCP ont même une amélioration de 22 % sur des problèmes difficiles.

Cependant, l’amélioration la plus spectaculaire vient des problèmes quadratiques (MIQP) non convexes : les modèles les plus difficiles prennent 65 % de temps en moins ! Pour les autres catégories de problèmes, quand on ignore le fait que certaines variables soient entières, on peut trouver la solution optimale en des temps raisonnables ; dans le cas non convexe, cette propriété n’est plus vérifiée et trouver la solution optimale en variables continues est déjà un challenge en soi. L’amélioration provient des plans sécants par reformulation-linéarisation.

Décomposition de Benders

Certains problèmes ont une structure décomposable, c’est-à-dire qu’on peut les résoudre par blocs relativement indépendants. Par exemple, dans un problème stochastique, on prend une série de décisions que l’on évalue dans une série de situations : ces évaluations sont indépendantes les unes des autres. Dans ce genre de cas (et bien d’autres), une décomposition de Benders peut s’appliquer : les décisions principales correspondront à un nœud racine, les évaluations à des sous-problèmes.

Cependant, cette décomposition est loin d’être facile à implémenter — il faut appliquer la théorie de la dualité pour faire passer l’information des sous-problèmes à la racine et vice-versa. Cette nouvelle version de CPLEX propose d’automatiser en grande partie cette étape, selon plusieurs modes d’opération : laisser CPLEX s’occuper entièrement de la décomposition (choisir les variables du problème racine et des sous-problèmes), proposer soi-même une première décomposition et laisser CPLEX la retravailler (diviser les sous-problèmes), entièrement spécifier la décomposition.

Selon les types de problème, cette décomposition automatique peut apporter un certain bénéfice ou pas : pour le jeu de tests habituel de CPLEX, cinq pour cent des problèmes prenant plus de dix secondes de calcul voient une amélioration. Par contre, sur des problèmes où la décomposition de Benders est bien mieux adaptée, les effets sont plus visibles : une résolution trois fois plus rapide sur tous les problèmes du jeu de tests spécifique, dix fois plus pour les plus ardus (temps de résolution supérieur à cent secondes).

D’après des tests indépendants, cette fonctionnalité fonctionne très bien : elle n’est pas plus lente qu’une implémentation manuelle, même en laissant CPLEX choisir la meilleure manière d’effectuer la décomposition (au niveau des temps de démarrage, avant le début de la résolution du problème, apporter des annotations semble néfaste). Ainsi, pour la plupart des utilisateurs, rien ne justifie vraiment l’investissement dans une implémentation de cette décomposition : le solveur le fait très bien lui-même.

Aides à la modélisation

Écrire des programmes d’optimisation complexes n’est pas forcément une mince affaire, CPLEX propose de prémâcher une partie du travail. Notamment, un nouveau paramètre demande au solveur d’analyser le problème et de proposer des améliorations — par exemple, remplacer des contraintes avec des constantes assez grandes (“big-M”) par des contraintes indicatrices.

CPLEX Warning 1042: Detected a variable bound 
constraint with large coefficients. Constraint 
c8101, links binary variable x934 with variable 
x2642 and the ratio between the two is 1e+06. 
Consider turning constraint into an indicator 
for better performance and numerical stability.

Cette fonctionnalité vient compléter l’analyse de la dégénérescence lors des calculs. La dernière version propose également d’analyser, de manière automatique, la variabilité de performance — ce qui indique probablement quelques problèmes dans la modélisation.

La modélisation des fonctions linéaires par morceau est maintenant accessible tant en C et Python que dans les fichiers LP (c’était déjà le cas en C++, C# et Java).

Sources et images : Recent advances in IBM ILOG CPLEX @INFORMS 2016, What’s in CPLEX Optimization Studio 12.7?, IBM CPLEX Optimization Studio 12.7 – Benders, Modeling Assistance, etc.

Sortie de MOSEK 8.0

En ce début d’année, MOSEK annonce la version 8.0 finale de son solveur d’optimisation mathématique (les premières préversions sont arrivées en mai dernier). Contrairement à Gurobi ou d’autres, MOSEK a la particularité de se focaliser sur des problèmes non linéaires, principalement continus (même s’il est possible d’ajouter des variables entières). Ainsi, MOSEK est le solveur commercial de référence pour les problèmes convexes, le seul à traiter aussi bien des problèmes coniques quadratiques (SOCP) — ce qui est relativement courant — que semidéfinis positifs (SDP).

Du côté des solveurs, cette nouvelle version apporte son lot d’améliorations de performance (mesurée notamment par les temps d’exécution et la précision des solutions), notamment pour les programmes semidéfinis positifs (le solveur par point intérieur est nettement plus stable, numériquement parlant). Ainsi, les temps de résolution sont réduits en moyenne de 40 % sur des problèmes de taille moyenne (de l’ordre de la minute de temps de calcul) et de grande taille. MOSEK trouve aussi une solution dans nettement plus de cas ; alors qu’il jouait dans la même cour que les solveurs académiques les plus avancées (SDPT3 et SeDuMi) avec sa version précédente, MOSEK 8 devient significativement plus rapide sur un grand nombre de problèmes. En termes marketing, les problèmes semidéfinis positifs deviennent accessibles dans la plupart des cas.

Désormais, les programmes quadratiques et avec des contraintes quadratiques convexes sont automatiquement reformulés comme des problèmes coniques, ce qui permet d’appliquer le solveur conique : les temps de résolution sont moindres (amélioration de l’ordre de 40 %), la solution est obtenue avec une meilleure robustesse. MOSEK peut aussi maintenant dualiser de manière automatique des problèmes coniques quadratiques (le travail se poursuit pour les problèmes semidéfinis positifs).

Le présolveur a aussi fait l’objet de quelques attentions, ce qui a fortement amélioré sa performance : en particulier, ses mises à l’échelle sont nettement plus agressives que précédemment. Il est plus efficace sur les problèmes coniques quadratiques. L’éliminateur de variables a été complètement réécrit : il est ainsi plus rapide et consomme moins de mémoire. Pour les problèmes avec des variables entières, le présolveur peut maintenant être relancé après l’addition de plans sécants, si le solveur trouve que cette opération peut être utile.

En dehors du solveur par point intérieur, le code de MOSEK a été largement nettoyé. Ainsi, deux implémentations du simplexe ont été supprimées : la version primale dans les réseaux et la version primale-duale ont été supplantés par un simplexe dual. Les fonctionnalités de priorité de branchement ont été supprimées des solveurs en nombres entiers, étant rarement utilisées.

Source : Recent Advances In The New Mosek  8 (figure), Major changes in MOSEK 8.0.

Sortie de Gurobi 7.0

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.

Sortie de Gurobi 6.0

Gurobi est l’un des meilleurs solveurs en programmation mathématique existants, ce qui le rend très intéressant pour la recherche opérationnelle. Il se montre également versatile : il gère les problèmes avec des variables continues et discrètes, avec une structure linéaire ou quadratique. Il est notamment utilisé pour assigner les vols aux comptoirs d’enregistrement et aux portes d’embarquement à l’aéroport de Copenhague, mais aussi pour des recherches sur l’équilibre entre la demande en électricité et la production renouvelable.

Sa version 6.0 apporte bien évidemment des améliorations de performances intéressantes (jusqu’une trentaine de pour cent de temps économisé pour des problèmes linéaires en nombres entiers — MIP — difficiles), mais aussi de nouvelles fonctionnalités algorithmiques : les objectifs linéaires par morceaux peuvent être indiqués directement au solveur, ce qui conduit à d’importantes améliorations de performances par rapport à une modélisation plus classique.

Le solveur distribué est également amélioré : pour résoudre un MIP, il était possible d’exploiter plusieurs machines en lançant la résolution avec des paramètres différents sur chaque machine (concurrent optimiser) ; désormais, ces machines pourront également collaborer sur une même instance du problème (distributed MIP solver). Selon les problèmes à résoudre, cette technique pourrait être plus rapide.

Parmi les autres améliorations, on peut noter que les matrices des contraintes pourront contenir plus de deux milliards d’éléments non nuls. De nouvelles méthodes permettent également l’optimisation asynchrone, afin de lancer d’autres tâches pendant que le solveur travaille. Les fonctions de retour pourront également ajouter des contraintes retardées (lazy), une indication supplémentaire par rapport aux plans sécants déjà disponibles.

Source : http://www.gurobi.com/products/gurobi-optimizer/what%27s-new-in-v6.0