Peel and Bound: Solving Discrete Optimization Problems with Decision Diagrams and Separation

Cette thèse présente des avancées significatives dans la théorie et l’implémentation des méthodes d’optimisation basées sur les diagrammes de décision : tout d’abord le développement et l’amélioration de l’algorithme Peel-and-Bound (PnB) comme une étude sur la construction d’un solveur utilisant des diagrammes de décision (DD), et l’introduction de DD relaxés implicites qui généralise une idée cruciale pour l’implémentation efficace de PnB. Les DD relaxés sont un outil graphique pour construire des bornes de relaxation combinatoires pour des problèmes d’optimisation. L’algorithme PnB démontre le potentiel puissant des solveurs basés sur les DD exploitant la séparation, une méthode de construction de DD relaxés partant d’un petit DD représentant une relaxation initiale faible qui est ensuite améliorée par division de nœuds. PnB est un algorithme hautement parallélisable, construit autour de la production de DD relaxés par séparation, qui peut échanger toute la mémoire disponible contre de l’efficacité de calcul. L’implémentation de PnB a été testée sur les 467 instances de référence du problème du voyageur de commerce avec fenêtre de temps (TSP-TW) utilisées pour tester le solveur branch-and-bound (BnB) ddo basé sur les DD. Même lorsque ddo utilise le calcul parallèle, PnB surpasse ddo. De plus, PnB a résolu 15 instances qui, à notre connaissance, étaient ouvertes dans la littérature. Dans notre test final de PnB, nous avons exécuté la nouvelle implémentation de PnB sur la variante du makespan des 467 instances du TSP-TW. PnB a résolu 94 % des instances de makespan, et 3 % supplémentaires lorsqu’il était initialisé avec la meilleure solution connue. L’implémentation de l’algorithme PnB a montré des performances de pointe sur les instances de référence du TSP-TW, surpassant le solveur branch-and-bound basé sur les DD existant. Cette thèse fait progresser davantage les méthodes d’optimisation basées sur les DD en généralisant le concept de DD relaxés implicites, une méthode générique de génération de DD qui ne nécessite pas que les arcs soient étiquetés. Au lieu de cela, cette information est déplacée vers les nœuds. Les DD relaxés implicites sont une méthode facile à implémenter pour obtenir des accélérations massives dans les solveurs basés sur les DD. Ce concept a été crucial pour atteindre des résultats de pointe avec notre implémentation de PnB. L’utilité de PnB et des DD relaxés implicites a été démontrée par une application au problème de routage d’astéroïdes (ARP). Ce problème peut être considéré comme une variante du célèbre problème du voyageur de commerce où toutes les villes (astéroïdes) sont dans l’espace, et donc en mouvement constant. L’algorithme trouve des solutions réalisables de haute qualité pour plusieurs instances de l’ARP, dont beaucoup sont optimales sous une légère hypothèse sur la qualité de l’optimiseur interne. C’est la première méthode dans la littérature plus efficace que la force brute pour trouver des solutions exactes aux problèmes d’optimisation de trajectoire globale comme l’ARP. Le cadre définissant l’algorithme est polyvalent, hautement évolutif et applicable à une large gamme de problèmes de séquençage exigeants en complexité. Cette thèse non seulement fait progresser la compréhension et l’application des DD à travers l’introduction de méthodes innovantes comme le peel-and-bound et les DD relaxés implicites, mais elle ouvre également la voie à de futures percées dans des défis d’optimisation complexes qui nécessitent de résoudre un problème d’optimisation combinatoire externe comportant un problème d’optimisation interne coûteux en calcul.