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.
Et vous ?
Que pensez-vous de cette nouvelle version de CPLEX ?Voir aussi
Une présentation de CPLEX 12.8 Une présentation du nouveau système de fonctions de rappel