OscaR.cbls

Un moteur d’optimisation de recherche locale open source mettant en œuvre la recherche locale basée sur des contraintes en Scala.
Pour plus d’informations, consultez notre dépôt Github.

Pourquoi la recherche locale ?

La recherche locale est une technique d’optimisation polyvalente et évolutive pour résoudre des problèmes de recherche opérationnelle. Elle est, par exemple, bien adaptée aux problèmes d’optimisation avec un grand espace de recherche, tels que les problèmes d’optimisation de routage.

Elle peut également intégrer facilement des algorithmes dédiés tels que les graphes ou la géométrie computationnelle.

La recherche locale englobe également des métaheuristiques telles que la recherche tabou, le redémarrage, le recuit simulé, la destruction et la reconstruction, la recherche locale généralisée, les chaînes d’éjection, le VLSN, etc.

Pourquoi OscarR.cbls ?

Développer une solution de recherche locale est souvent coûteux car :

• Développer des contraintes efficaces est complexe car cela repose sur une évaluation incrémentale des contraintes.
• Une procédure de recherche dédiée doit être élaborée, et elle doit prendre en compte la structure du problème.

OscaR.cbls est une librairie logicielle qui permet de largement réduire ces coûts de développement.

OscaR.cbls est un outil intelligent pour les ingénieurs en optimisation. Il est fourni sous forme de bibliothèque logicielle open source (LGPL). Programmer en Scala ou en Java est nécessaire pour développer une solution basée sur OscaR.cbls. Quelques exemples sont fournis.

Pour utiliser OscaR.cbls, il est nécessaire de connaître les préceptes de la recherche locale et des métaheuristiques, notamment, afin d’élaborer et paramétrer les modèles et les procédures de recherche dans des applications spécifiques.

Philosophie générale d’OscarR.cbls

OscaR.cbls repose sur la philosophie générale suivante :

• Se concentrer sur la complexité computationnelle et fournir une API bien pensée pour obtenir une bonne complexité computationnelle globale, quelle que soit l’application.
• Offrir un support maximal, à la fois pour la modélisation et la résolution. Il est donc nécessaire de programmer en Scala ou Java pour utiliser OscaR.cbls.
• OscaR.cbls pourrait se résumer à comment investir au mieux le temps de cerveau disponible. OscaR.cbls permet de se concentrer pour :
  • Élaborer un modèle approprié d’un problème métier complexe sans perdre de temps dans la mise en œuvre.
  • Rapidement concevoir et étudier diverses procédures de recherches et métaheuristiques pour identifier la combinaison la mieux adaptée au cas considéré et à ses contraintes.

Principales fonctionnalités d’OscarR.cbls

La recherche locale, c’est la modélisation (modeling) avec la procédure de recherche (searching).

OscaR.cbls offre un support avancé à la fois pour la modélisation et la procédure de recherche :

• Modélisation basée sur les contraintes (constraint-based modeling)
  • Intègre des algorithmes très efficaces pour évaluer les solutions basées sur l’évaluation incrémentale, les pré-calculs, les caches, etc.
• Procédure de recherche basée sur les combinateurs (combinator-based searching)
  • Une procédure de recherche locale doit être conçue pour chaque cas d’utilisation, nous avons donc facilité la définition de toute procédure de recherche locale et métaheuristique en l’assemblant à partir d’une bibliothèque d’éléments standards.

Origines d’OscarR.cbls

OscaR.cbls a débuté en 2011 et a évolué au fil de projets industriels et de recherche. L’objectif global était de structurer les résultats de recherche pertinents issus du milieu académique dans un solveur propre et bien structuré.

Il a évolué au fil des années et divers aspects ont été ajoutés, notamment :

• Combinateurs de recherche [Del18]
• Optimisation de routage basée sur des séquences [Del18b]
• Mécanismes pour développer de nouvelles contraintes globales basées sur des fonctions de transition [Del21c]
• Recherche distribuée [Os21,Os22]
• Informations de profilage

En 2024, nous avons commencé une réécriture en profondeur d’OscaR.cbls. Celui-ci ayant été initialement développé comme prototype de recherche, divers modules reposaient sur des technologies obsolètes. Début 2025, nous avons présenté la première version prête pour la production d’OscaR.cbls. Elle comprend notamment une API de référence qui a été conçue pour être stable face aux évolutions futures d’OscaR.cbls.

Modélisation basée sur des contraintes

OscaR.cbls propose trois types de variables : Int, IntSet et IntSequence.
IntSequence est un type particulier de variable pour représenter les itinéraires de véhicules ; voir section Optimisation de routage ci-dessous pour plus de détails.
OscaR.cbls offre une riche bibliothèque de contraintes efficaces sur ces variables, y compris :

• Arithmétique : sum, prod, somme sur une plage sélectionnée d’éléments
• Min-max : min, max, argmin, argmax
• Logique : element
• Ensemble : intersection, union
• Spécifique au routage : routeLength, routeFlatMap

Consultez notre API pour la liste complète des contraintes proposées.

Recherche basée sur des combinateurs

La recherche locale nécessite une procédure de recherche. Cette procédure doit prendre en compte le problème à résoudre.

OscaR.cbls offre une approche unique où une procédure de recherche est élaborée en combinant des voisinages de recherche avec des combinateurs de voisinage [Del18].

• Exemples de voisinages de recherche :
  • Domain-independent : Assign, Swap, Roll, Shift
  • Routage : InsertPoint, 1-opt, 2-opt, 3-opt
• Les combinateurs permettent d’introduire divers aspects dans la procédure de recherche, tels que :
  • Sélection de voisinage : Round Robin, BestSlopeFirst (sur le principe de l’ascension de colline), etc.
  • Critère d’arrêt : timeout, maxMoves
  • Métaheuristiques : restart, simulated annealing, late acceptance
  • Divers : afterMove, showObjectiveFunction, etc.

OscaR.cbls offre également un support pour l’élaboration de la procédure de recherche, notamment :

• Informations de profilage détaillées sur les différentes parties de la procédure de recherche.
• Interface avec iRace (à venir).

Consultez notre API pour connaître la liste complète des combinateurs.

Optimisation de routage

L’optimisation de routage est une utilisation courante de l’optimisation par recherche locale.

OscaR.cbls offre un support spécifique pour l’optimisation de routage, basé sur notre article [Del18b], à savoir :

• Un type spécifique de variable, la séquence d’entiers, qui représente un itinéraire et fournit une structure de données efficace et des notifications delta symboliques pour les contraintes globales.
• Une bibliothèque de contraintes avec des algorithmes de contraintes globales qui effectuent des calculs symboliques, atteignant ainsi couramment une complexité de O(log n) [Del21c].
• Une bibliothèque de voisinages classiques tels que 1-opt, 2-opt, 3-opt, etc.
• Visualisation graphique.

Références

[Del18] De Landtsheer, R., Guyot, Y., Ospina, G., Ponsard, C. (2018). Combining Neighborhoods into Local Search Strategies. In : Amodeo, L., Talbi, EG., Yalaoui, F. (eds) Recent Developments in Metaheuristics. Operations Research/Computer Science Interfaces Series, vol 62. Springer, Cham. https://doi.org/10.1007/978-3-319-58253-5_3

[Del18b] Renaud De Landtsheer, Yoann Guyot, Gustavo Ospina, Fabian Germeau, Christophe Ponsard, Reasoning on Sequences in Constraint-Based Local Search Frameworks, 15th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR), Delft, The Netherlands, June 26-29, 2018 https://www.cetic.be/Reasoning-on-Sequences-in-Constraint-Based-Local-Search-Frameworks

[Del21c] De Landtsheer, R., Germeau, F., Fayolle, T., Ospina, G., Ponsard, C. (2021). Generic Support for Precomputation-Based Global Routing Constraints in Local Search Optimization. In : Yalaoui, F., Amodeo, L., Talbi, EG. (eds) Heuristics for Optimization and Learning. Studies in Computational Intelligence, vol 906. Springer, Cham. https://doi.org/10.1007/978-3-030-58930-1_10

[Os21] Ospina, Gustavo & De Landtsheer, Renaud. (2021). Towards Distributed Local Search Through Neighborhood Combinators, in Proceedings of the 10th International Conference on Operations Research and Enterprise Systems - ICORES, 248-255, 2021, https://www.cetic.be/Towards-Distributed-Local-Search-Through-Neighborhood-Combinators

[Os22] Ospina, G., De Landtsheer, R. Defining Parallel Local Search Procedures with Neighborhood Combinators. SN COMPUT. SCI. 3, 231 (2022). https://doi.org/10.1007/s42979-022-01120-1