View article

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 …