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

This thesis presents significant advancements in the theory and implementation of Decision-Diagram-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.