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.

Advertisements

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