Large Scale Optimization using Decomposition

• Analyze mathematical optimization models.
• Understand and apply linear programming duality in algorithm developement.
• Apply modeling software to implement iterative algortihms
• Understand and apply lowerbounding methods.
• Decompose mathematical models such that these can be solved iteratively.
• Apply the Benders decomposition algorithm.
• Apply the Column Generation algorithm/Dantzig-Wolfe decomposition.
• Understand the correctness of Benders decompositions algorithm and Dantzig-Wolfe decomposition algorithm
• Implement of basis versions of Benders decomposition algorithm and Dantzig-Wolfe decomposition algorithm
• Summarize and explain a scientific article on decomposition algorithms

Many important optimization problems can be modeled using mixed
integer programming models. When these models cannot be solved using
standard solver software, decomposition algorithms can be applied to solve the problems iteratively. The methods are:
– Benders decomposition
– Dantzig-Wolfe decomposition/column generation

The course will give the students a thorough introduction to the two
types of algorithms and enable to use them as solution methods for
various problems.

42112, The programming language Julia, using the Math. Programming package Jump will be used in the exercises and in the assignments.

Lectures, excercises and project work.

The course is quantitatively oriented, and a good understanding of linear programming is necessary. In the exercises, the computer language Julia/JuMP (taught in course 42112) is used to implement the decompositions algorithms. Students without prior knowledge of Julia/JuMP should be prepared for a significant extra workload.