Decomposition Approaches for Optimization Problems

This dissertation encompasses the development of decomposition approaches for a variety of both real-world and fundamental optimization problems. Many optimization problems comprise of multiple interconnected subproblems, often rendering them too large or too complicated to solve as a single integral problem. Decomposition approaches are required to deal with these problems efficiently. By decomposing a problem into multiple subproblems, efficient dedicated procedures can be employed to solve the subproblems independently. Furthermore, often strong bounds on the optimal solutions can be derived by exploiting structures in the underlying subproblems.This work primarily focuses on analyzing and identifying problem components to decompose a problem into multiple, easier-to-solve, subproblems. The actual decompositions are obtained through mathematical techniques such as Column Generation and Benders decomposition, thereby relying on Integer Programming, Constraint Programming, heuristic and combinatorial procedures to solve the resulting subproblems. Each solution method is developed with scalability and extendability in mind, while simultaneously making the methods sufficiently robust to account for changes to the original problem definitions. Moreover the decomposition strategies are designed to preserve a notion of optimality, thereby providing insight into the quality of a solution.From an application point of view, the present work is centered around four routing and scheduling problems: the School Bus Routing Problem (SBRP), the Concrete Delivery problem (CDP), the Time-Dependent TSP (TD-TSP) and the Balanced TSP (BTSP). For each of these problems, decomposition strategies have been developed. The SBRP and BTSP are solved via a branch-and-price framework; lower bounds on the SBRP are derived through Lagrangian Relaxation. A Benders decomposition is developed for the CDP. The subproblems resulting from the Benders decomposition are efficiently solved through Integer and Constraint programming, in combination with a fast scheduling heuristic. Finally, a generic, robust Constraint Programming approach, strengthened with Multivariate Decision Diagrams, is implemented for the TD-TSP. To improve domain propagation, bounds derived from alternative problem relaxations are incorporated in the CP search through an additive bounding procedure. To validate the aforementioned solution approaches, experiments are conducted on real-world or simulated data.By decomposing a problem, techniques from various interdisciplinary domains can be combined into an integrated solution approach. Correlations between the problems under consideration as well as the proposed solution methodologies provide insight as to the applicability, limitations and the intuition behind the various techniques. It are exactly these insights that ultimately will lead to fully automated problem solvers, capable of analyzing and decomposing optimization problems without human interference.status: publishe