Projects per year
Abstract
Many reallife planning and decision making problems can be formulated as mathematical optimization models. Depending on the scope of the problem, finding good solutions can be highly profitable; in 2009 the entire Dutch railway timetable was reconstructed from scratch resulting in an annual revenue increase of 40 million euros.
In general, such optimization models can be extremely difficult to solve due to their complexity or sheer size. For specifically structured problems reformulation and decomposition the techniques can be used to improve tractability. This might result in new information about the potential revenue gains or cost reductions or may even lead to optimal solutions that would otherwise be impossible to obtain. This thesis thoroughly investigates a specific decomposition technique known as DantzigWolfe reformulation.
A major contribution of this thesis is the introduction of the linking cuts. Linking cuts are valid inequalities to be added to a DantzigWolfe reformulation with binary linking variables. The thesis presents a theorem that states that under certain conditions on the structure of the decomposition, the linking cuts ensure optimal integer solutions when added to the relaxation of the DantzigWolfe reformulation. The cuts are implemented in a branchandcutandprice framework, and their effectiveness is proven through a number of computational experiments. They provide stateoftheart solutions to both the temporal knapsack problem as well as the image restoration problem, and their potential is further shown on a set of generic mixed integer programs. The thesis also expands on the known applications of DantzigWolfe reformulation by providing effective decomposition ideas for unconstrained binary polynomial programs. Finally, AutoDec, a tool for automatic branchandcutandprice, was developed. Given an optimization model and a set of specifications of how the model should be decomposed, AutoDec automatically implements DantzigWolfe reformulation and solves the model. AutoDec makes it easy for students and researchers to experiment with the techniques developed in this thesis.
In general, such optimization models can be extremely difficult to solve due to their complexity or sheer size. For specifically structured problems reformulation and decomposition the techniques can be used to improve tractability. This might result in new information about the potential revenue gains or cost reductions or may even lead to optimal solutions that would otherwise be impossible to obtain. This thesis thoroughly investigates a specific decomposition technique known as DantzigWolfe reformulation.
A major contribution of this thesis is the introduction of the linking cuts. Linking cuts are valid inequalities to be added to a DantzigWolfe reformulation with binary linking variables. The thesis presents a theorem that states that under certain conditions on the structure of the decomposition, the linking cuts ensure optimal integer solutions when added to the relaxation of the DantzigWolfe reformulation. The cuts are implemented in a branchandcutandprice framework, and their effectiveness is proven through a number of computational experiments. They provide stateoftheart solutions to both the temporal knapsack problem as well as the image restoration problem, and their potential is further shown on a set of generic mixed integer programs. The thesis also expands on the known applications of DantzigWolfe reformulation by providing effective decomposition ideas for unconstrained binary polynomial programs. Finally, AutoDec, a tool for automatic branchandcutandprice, was developed. Given an optimization model and a set of specifications of how the model should be decomposed, AutoDec automatically implements DantzigWolfe reformulation and solves the model. AutoDec makes it easy for students and researchers to experiment with the techniques developed in this thesis.
Original language  English 

Number of pages  202 

Publication status  Published  2021 
Fingerprint
Dive into the research topics of 'Automatic DantzigWolfe Reformulation of Mixed Integer Linear Programs'. Together they form a unique fingerprint.Projects
 1 Finished

Automatic Decomposition of Mixed Integer Linear Programs
Clausen, J. V., Desaulniers, G., Irnich, S., Larsen, J., Lusby, R. M., Røpke, S. & Lübbecke, M.
01/09/2017 → 03/06/2021
Project: PhD