[Recherche opérationnelle] Sortie de MOSEK 8.0

Le solveur conique par point intérieur fortement amélioré : les temps de calcul réduits de 40 %

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.