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.

Abstract

This thesis presents significant advancements in the theory and implementation of DecisionDiagram-based optimization methods: primarily the development and enhancement of the Peel-and-Bound (PnB) algorithm as a study in how to construct a solver using Decision Diagrams (DDs), and the introduction of implicit relaxed DDs which generalizes an idea critical to efficient implemention of PnB. Relaxed DDs are a graphical tool for constructing combinatorial relaxed bounds for optimization problems. The PnB algorithm demonstrates the powerful potential of DD-based solvers that leverage separation, a method of constructing relaxed DDs by starting from a small DD representing a weak initial relaxation and improving that relaxation by splitting nodes. PnB is a highly parallelizable algorithm, built around constructing relaxed DDs by separation, which can trade memory for computational efficiency. The PnB implementation was tested on the 467 benchmark instances of Traveling Salesman Problem with Time Windows (TSP-TW) used to test the DD-based branch-and-bound (BnB)solver (ddo). Even when ddo is using parallel processing, PnB outperforms ddo. Furthermore,PnB closed 15 instances that, to the best of our knowledge, were open in the literature. In our final test of PnB, we ran the new implementation of PnB on the makespan variant of the 467 TSP-TW instances. PnB closed 94% of the makespan instances, and an additional 3% when seeded with the best known solution. The implementation of the PnB algorithm had a cutting-edge performance on the benchmark instances of the TSP-TW, outperforming the existing DD-based branch-and-bound (BnB) solver. This thesis further advances DD-based optimization methods by generalizing the concept of implicit relaxed DDs, a generic method of generating DDs that does not require the arcs to be labeled. Instead, information that would have been stored in arc labels is moved to the nodes. Implicit relaxed DDs are an easy-to-implement method for achieving massive speed-ups in DD-based solvers. This concept was critical to achieving cutting edge results with our PnB implementation. The utility of both PnB and implicit relaxed DDs was demonstrated with an application to the Asteroid Routing Problem (ARP). This problem can be thought of as a variant of the well-known Travelling Salesman Problem where all of the cities (asteroids) are in Space, and thus in constant motion. The ARP has an outer combinatorial problem that requires finding the optimal permutation to visit the asteroids, and an inner non-linear non-convex optimization problem that requires computing the optimal trajectory between two asteroids at specific points in time. The algorithm finds high-quality feasible solutions for several instances of the ARP, many of which are optimal under a mild assumption about the quality of the inner optimizer. This is the first method in the literature more efficient than brute force for finding exact solutions to global trajectory optimization problems like the ARP. The framework defining the algorithm is versatile, highly scalable, and applicable to a diverse range of computationally demanding sequencing problems. This thesis not only advances the understanding and application of DDs through the introduction of innovative methods like peel-and-bound and implicit relaxed DDs, but also sets the stage for future breakthroughs in complex optimization challenges that require solving an outer combinatorial optimization problem that has a computationally expensive inner optimization problem.