1 Optimisation basée sur des Diagrammes de Décision (DDO)
DDOLib [1] est une bibliothèque Java destinée à la résolution de problèmes de minimisation
discrète via la Programmation Dynamique [2]. En implémentant un modèle, l'utilisateur spé-
cifie la représentation de l'état, la fonction de transition ainsi que la structure de coût, et le
solveur orchestre automatiquement la recherche. Une bibliothèque de modélisation suivant ce
paradigme a été introduite dans le solveur DDO [9], dans le solveur DDIP [11], ou encore les
solveurs CODD [12], mais DDOLib a l'ambition de tous les unifier.

Conceptuellement, la résolution du programme dynamique équivaut à la recherche du plus
court chemin dans un graphe acyclique stratifié (ou en couches), partant d'un état initial
vers un état terminal désigné. Un large éventail d'algorithmes a été développé pour résoudre
les problèmes de plus court chemin tout en évitant de développer explicitement l'ensemble
de l'espace de recherche. DDOLib prend en charge plusieurs stratégies de recherche informée
à cette fin, notamment A* [10], mais aussi des algorithmes complets de type "anytime" tels
que le Anytime Column Search [13] ou le Anytime Weighted A* [14]. Ces approches deviennent
particulièrement efficaces lorsque l'utilisateur fournit une heuristique admissible ou consistante,
offrant une estimation optimiste du coût restant pour atteindre l'état cible.

Au-delà de la programmation dynamique classique basée sur la recherche, DDOLib intègre
des techniques de résolution basées sur les diagrammes de décision [3, 4]. En explorant l'es-
pace d'états par séparation et évaluation (branch-and-bound), cette approche entrelace deux
diagrammes de décision à largeur bornée. Le premier est le diagramme de décision restreint,
obtenu en écartant les états les moins prometteurs, ce qui fournit des bornes supérieures pri-
males. Le second est le diagramme de décision relaxé, obtenu par fusion d'états, produisant une
borne inférieure duale. Ce dernier nécessite, en plus de la fonction de transition, que l'utilisa-
teur définisse un opérateur de fusion d'états pour combiner les nœuds lors de la construction
du diagramme.

De plus, DDOLib intègre toutes les avancées récentes associées à ces méthodes basées sur les
diagrammes de décision, incluant, entre autres, les mécanismes de mise en cache [5], la détection
de dominance [6] et le calcul de bornes locales [7]. Un autre mécanisme présent dans DDOLib
est la Fast Lower Bound [7] : calculer rapidement une borne inférieure afin d'augmenter le
nombre de nœuds élagés.

Pour être mise en œuvre, l'approche DDO nécessite que l'utilisateur développe du code
spécifique, notamment pour la Fast Lower Bound. Une erreur dans ces fragments de code
entraîne des sous-optimalités ou d'autres erreurs, qui sont difficiles à détecter. DDOLib contient
des aides au débogage, aidant l'utilisateur à corriger ses erreurs.

2 Conclusions et perspectives
DDO peut s'avérer efficace pour résoudre des problèmes d'optimisation fortement contraints,
notamment des problèmes de séquençage. DDOLib fournit divers outils pour implémenter un
solver basé sur cette technologie.

Cette librairie est encore en cours de développement et s'enrichit régulièrement de nouvelles
fonctionnalités. Prochainement, des variantes du Large Neighborhood Search seront implémen-
tées [8]. Il est également prévu de retravailler l'API utilisateur, notamment via un portage en
Scala. D'autres mécanismes, tels que le calcul distribué, sont également envisagés.

Dans cette présentation, nous illustrons comment utiliser DDOLib à travers divers exemples,
notamment le célèbre problème du sac à dos binaire, divers problèmes d'ordonnancement sur
machine unique, ainsi que le problème du voyageur de commerce avec fenêtres de temps.

Remerciements : Ce travail est soutenu par le projet Win4Collective DDOLib de la région
wallonne (projet 2410118).
Références
[1] DDOLib website. https://github.com/DDOLIB-CETIC-UCL/DDOLib.
[2] Richard Bellman. The theory of dynamic programming.
60(6) :503–515, 1954.
Bull. Amer. Math. Soc.,
[3] David Bergman, Andre A. Cire, Willem-Jan Van Hoeve, and John Hooker. Decision
Diagrams for Optimization. Springer, 2016.
[4] David Bergman, Andre A. Cire, Willem-Jan Van Hoeve, and John N. Hooker. Discrete
optimization with decision diagrams. IJOC, 28(1) :47–66, 2016.
[5] Vianney Coppé, Xavier Gillard, and Pierre Schaus. Decision diagram-based branch-and-
bound with caching for dominance and suboptimality detection. IJOC, 36(6) :1522–1542,
2024.
[6] Vianney Coppé, Xavier Gillard, and Pierre Schaus. Modeling and exploiting dominance
rules for discrete optimization with decision diagrams. In CPAIOR, 2024.
[7] Xavier Gillard, Vianney Coppé, Pierre Schaus, and André A. Cire. Improving the filtering
of branch-and-bound mdd solver. In CPAIOR, 2021.
[8] Xavier Gillard and Pierre Schaus. Large neighborhood search with decision diagrams. In
IJCAI, 2022.
[9] Xavier Gillard, Pierre Schaus, and Vianney Coppé. Ddo : A generic and efficient framework
for mdd-based optimization. In IJCAI, pages 5243–5245, 2021.
[10] Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. A formal basis for the heuristic
determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern., 4(2) :100–107,
1968.
[11] Ryo Kuroiwa and J. Christopher Beck. Domain-independent dynamic programming :
Generic state space search for combinatorial optimization. In ICAPS, volume 33, 2023.
[12] Laurent Michel and Willem-Jan van Hoeve. Codd : A decision diagram-based solver for
combinatorial optimization. ECAI, 2024.
[13] Satya G. Vadlamudi, Piyush Gaurav, Sandip Aine, and P. P. Chakrabarti. Anytime column
search. In AJCAI, 2012.
[14] Rong Zhou and Eric A. Hansen. Multiple sequence alignment using anytime a*. In AAAI,
pages 975–977, 2002.