Decomposition of Integer Programs with Matchability Structure

• Dekomposition von Ganzzahligen Programmen mit Matching Struktur

Dahms, Florian H. W.; Koster, Arie Marinus (Thesis advisor); Krumke, Sven O. (Thesis advisor); Lübbecke, Marco (Thesis advisor)

Aachen : Lehrstuhl für Operations Research (2016, 2017)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2016

Abstract

The topic of the thesis are combinatorial optimization problems which have a matching problem as substructure. The following problems do have such a structure and are investigated in the thesis: the curriculum based time tabling problem, the multiple knapsack problem, the list coloring problem, a machine scheduling problem and a special railway shunting problem.It is shown, how the partial transversal polytope can be helpful in decomposing large integer programs into smaller sub problems. This decomposition can be seen as a Benders' decomposition. The theory of partial transversals is used to make the algorithms more efficient and numerically stable. The curriculum based time tabling problem is taken as an example for these algorithms. Here it is shown that even if the matching problem is based on hyper graph matchings, they can be solved within an acceptable time span using the algorithms of the thesis.For optimization problems which can be decomposed using Dantzig-Wolfe decomposition, the theory of the partial transversal is used to show that even non identical subproblems can be aggregated.

Institutions

• Department of Mathematics [110000]
• Discrete Optimization Teaching and Research Unit [113320]
• Chair of Operations Research [813310]