Automatic Dantzig-Wolfe Reformulation of Mixed Integer Linear Programs

Jens Vinther Clausen

Research output: Book/ReportPh.D. thesisResearch

2 Downloads (Pure)

Abstract

Many real-life 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 Dantzig-Wolfe reformulation.

A major contribution of this thesis is the introduction of the linking cuts. Linking cuts are valid inequalities to be added to a Dantzig-Wolfe 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 Dantzig-Wolfe reformulation. The cuts are implemented in a branch-and-cut-and-price framework, and their effectiveness is proven through a number of computational experiments. They provide state-of-the-art 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 Dantzig-Wolfe reformulation by providing effective decomposition ideas for unconstrained binary polynomial programs. Finally, AutoDec, a tool for automatic branch-and-cut-and-price, was developed. Given an optimization model and a set of specifications of how the model should be decomposed, AutoDec automatically implements Dantzig-Wolfe reformulation and solves the model. AutoDec makes it easy for students and researchers to experiment with the techniques developed in this thesis.
Original languageEnglish
Number of pages202
Publication statusPublished - 2021

Fingerprint

Dive into the research topics of 'Automatic Dantzig-Wolfe Reformulation of Mixed Integer Linear Programs'. Together they form a unique fingerprint.

Cite this