Bérengère Fally (BF) interviewe Renaud De Landtsheer (RDL) sur le développement d’un moteur d’optimisation par recherche locale, qui est sa contribution à OscaR, une librairie logicielle Open Source d’optimisation combinatoire.
BF : Qu’est-ce que OscaR ?
RDL : OscaR est une plate-forme générique de recherche opérationnelle regroupant les principaux moteurs d’optimisation combinatoire : CP (Constraint Programming), CBLS (Constraint-Based Local Search), MIP (Mixed Integer Programming) , DFO (derivative free optimization). OscaR comprend également une couche de visualisation permettant de rapidement comprendre et visualiser l’optimisation en action. D’autres algorithmes tels que des algorithmes de simulation et des algorithmes de graphes ou structures de données avancées sont également disponibles dans OscaR. On peut voir OscaR comme un véritable couteau suisse pour l’optimisation.
L’aspect combinatoire adresse spécifiquement les problèmes portant sur des variables discrètes. Par exemple, dans un problème d’optimisation de tournées de véhicule, on décide de l’ordre de visite des différents points à atteindre sur une journée par un véhicule.
OscaR se veut aussi être facile à utiliser et à intégrer. Par exemple, il est écrit en Scala, un langage de programmation productif, intégrable sans surcoût à toute application tournant sur la machine virtuelle Java.
BF : Quelle est la contribution du CETIC dans OscaR exactement ?
RDL : Le CETIC a développé le moteur d’optimisation de type « CBLS » ou « Constraint-Based Local Search ». Ce type de moteur est capable d’optimiser des problèmes combinatoires de très grande taille en un temps assez réduit, mais il n’est pas forcément capable d’arriver à l’optimum. En pratique, on peut atteindre des solutions de très bonne qualité en des temps acceptables, par exemple, plus de 90% d’optimalité en quelques secondes sur des problèmes de routage de taille réelle. Cela en fait un moteur très attractif pour des applications pratiques.
Nous avons de plus développé des modules permettant de résoudre des problèmes de type scheduling et routing. Le scheduling, c’est la planification de tâches en tenant compte de deadlines, et de ressources partagées. Le routing, c’est la planification de trajet de véhicule, par exemple pour la livraison de colis ou de mazout.
BF : Qui est impliqué dans OscaR ?
RDL : Les deux autres contributeurs principaux sont l’Université catholique de Louvain, et N-Side (une spin-off de l’UCL). L’équipe du professeur Pierre Schaus à l’UCL au sein du pôle INGI de l’UCL développe le moteur CP, le DFO, l’interfacage avec les solveurs MIP et la couche visualisation. Pierre Schaus et son équipe s’occupent également du maintien des tests et de la réalisation des releases.
N-Side travaille actuellement sur le moteur de simulation, donne régulièrement des pistes d’amélioration de la librairie et consacre du temps pour améliorer les modules de CP et MIP. Nous avons également reçu de l’aide de divers contributeurs tant académiques qu’industriels provenant notamment d’Angleterre et de Suède.
BF : et au sein du CETIC, qui collabore avec toi sur OscaR ?
Christophe Ponsard a contribué au moteur CBLS dès le début des développements, en développant des applications de test, et Yoann Guyot a mis en place une infrastructure de tests approfondis qui a permis de valider le moteur CBLS avant la release 1.0. Yoann a également contribué au développement du moteur de routing et de scheduling basés sur le moteur CBLS.
Nous avons également accueilli deux stagiaires de l’UMONS : Sébastien Drobisz qui a proposé une première version de parallélisation du moteur CBLS, et Florent Ghilain, qui a contribué à la première version du moteur de routage de véhicules. De nouveaux sujets de stages sont également régulièrement proposés sur notre site web.
BF : Pourquoi avoir développé un tel moteur CBLS ?
RDL : Tout d’abord parce qu’il y avait une niche inexploitée dans le paysage des moteurs d’optimisation. Il n’y avait pas de moteur de type CBLS open source disponible en 2011, date de début de ce projet. Par ailleurs, il n’y avait qu’un seul moteur CBLS commercial, à des prix de l’ordre de 7.000€ annuels.
Ensuite parce qu’un de nos projets demandait de résoudre rapidement des problèmes d’optimisation. Je me suis dit que plutôt que de développer un solveur spécifique pour ce projet, il serait plus rentable de développer un solveur générique capable entre autres de résoudre les problèmes posés par le projet de recherche.
Enfin, l’industrie européenne et wallonne peine actuellement à concurrencer l’industrie étrangère. Leur proposer des solutions d’optimisation de production permettrait d’améliorer la compétitivité industrielle sans toucher à l’outil existant. Un moteur de type CBLS est une solution possible aux types de problèmes rencontrés dans ce contexte industriel, dans la mesure où cela permet de résoudre de très gros problèmes dans un temps compatible avec les exigences de production.
BF : Qu’est-ce que OscaR peut apporter à l’industrie locale ?
RDL : On peut identifier deux types de sociétés potentiellement intéressées par OscaR :
BF : OscaR a donc déjà atteint un tel niveau de maturité qui permet de l’utiliser dans ces contextes industriels ?
RDL : Clairement : N-Side utilise déjà OscaR pour résoudre des problématiques d’optimisation complexes pour des grands groupes industriels internationaux : supply-chain dans les essais cliniques, sidérurgie, conception de réseau de distribution, …
Il faut savoir qu’Open Source et maturité industrielle ne sont pas incompatibles. Ainsi nous accordons beaucoup d’importance à la fiabilité d’OscaR. Chaque nuit OscaR est automatiquement testé sur des centaines d’exemples sur les serveurs de l’UCL afin d’éviter l’introduction de nouveaux bugs ou des dégradations de performances. La version 1.0.0 qui a été publiée en mars dernier se veut stable et la plupart des modules ont atteint un niveau de maturité suffisant pour être adoptés par les entreprises. Par ailleurs le niveau de maturité de chacun des modules est indiqué et les modules expérimentaux sont gérés dans des branches spécifiques et ne sont inclus dans une release qu’après avoir fait la preuve d’un niveau de maturité suffisante.
Au niveau des points plus faibles, la documentation au sens large (manuel, tutoriel, exemples...) reste encore assez sommaire mais cette situation va s’améliorer avec les prochaines releases qui devraient à présent se succéder à un rythme semestriel.
Un forum est également disponible. Et pour des demandes plus poussées, des collaborations spécifiques peuvent aussi voir le jour en lien avec des partenaires développant OscaR.
BF : Peux-tu m’en dire plus sur ces collaborations ?
Elles dépendent de la nature de la demande :
BF : Qu’est-ce qui t’attire personnellement dans ce type de projet ?
RDL : L’algorithmique confronte directement deux manières de raisonner, celle de la machine, extrêmement logique, mais dépourvue de vision globale, et l’humain, qui est capable d’avoir une vision globale, et est capable d’anticiper des tendances. Lorsque l’on développe des algorithmes tels que ceux d’OscaR, il faut sans arrêt faire des allers-retours entre ces deux manières de raisonner ; c’est un challenge que je trouve très prenant.
BF : Ton souhait ?
RDL : Qu’il y ait le plus possible d’applications utilisant OscaR, et pouvoir continuer à améliorer les performances du moteur CBLS.