Decomposition Methods (Not Offered in 2023-24)

Many combinatorial optimization problems arising in a variety of real-life applications can be modeled by using Mixed Integer Linear Programming (MILP) models. In principle, these models can be cast into a general-purpose MILP solver to find optimal or near-optimal solutions. To use such solvers, a decision maker does not need any knowledge on solution techniques to solve MILPs and can use them as black boxes. Nevertheless, these solvers are often unable to provide (near)optimal solutions of many large-scale instances of the magnitude of real-life applications in spite of the advanced solution techniques they embed. When the problem at hand is so difficult to solve, the decision maker has to develop a tailored solution method. In this course, we will discuss common solution methodologies and their of theoretical foundations. The main topics addressed are:

• The cutting plane method and branch-and-cut
• Lagrangian relaxation
• General purpose inequalities for (mixed) integer linear programs
• Total unimodularity and well-solved problems
• Dynamic programming
• Column generation and branch-and-price

If time allows we will also address further concepts such as Benders decomposition or optimization under uncertainty (stochastic or robust optimization).