Decomposition of Integer Programs with Matchability Structure

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

doi:36585

Decomposition of Integer Programs with Matchability Structure = Dekomposition von Ganzzahligen Programmen mit Matching Struktur

Dahms, Florian H. W.

2017 & 2016

Verantwortlichkeitsangabevorgelegt von Diplom-Mathematiker Florian Herbert Werner Dahms

ImpressumAachen : Lehrstuhl für Operations Research 2017

Umfang1 Online-Ressource (xii, 179 Seiten) : Illustrationen, Diagramme

Dissertation, RWTH Aachen University, 2016

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2017

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Koster, Arie Marinus (Thesis advisor) ; Krumke, Sven O. (Thesis advisor) ; Lübbecke, Marco (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2016-11-25

Online
DOI: 10.18154/RWTH-2017-08718
URL: http://publications.rwth-aachen.de/record/706540/files/706540.pdf
URL: http://publications.rwth-aachen.de/record/706540/files/706540.pdf?subformat=pdfa

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Dantzig-Wolfe Decomposition (frei) ; Koenig-Hall Theorem (frei) ; benders decomposition (frei) ; integer programming (frei) ; matchings (frei) ; polyhedra (frei) ; traversals (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
Die Dissertation beschäftigt sich mit kombinatorischen Optimierungsproblemen, denen eine Matching Struktur zugrunde liegt. Als Beispiele werden in der Arbeit die folgenden Probleme betrachtet: Das Curriculum basierte Stundenplanungsproblem, das Multiple Knapsack Problem, das List Coloring Problem, ein Machine Scheduling Problem, sowie ein spezielles Eisenbahn Rangierproblem.Es wird gezeigt, wie mithilfe des partiellen Transversal Polytops größere ganzzahlige Programme in kleine Teilprobleme zerlegt werden können. Diese Zerlegung kann als Benders' Dekomposition verstanden werden und ist generisch auf viele Probleme anwendbar. Die Theorie um die partiellen Transversale wird genutzt um den Dekompositionsalgorithmus effizienter und numerisch stabiler zu machen. Das Curriculum basierte Stundenplanungsproblem wird als Beispielanwendung für diese Algorithmen betrachtet. Hierbei wird unter anderem gezeigt, dass sich Stundenplanungsprobleme, bei denen das zugrunde liegende Matching ein bipartites Hypergraphenmatching ist, mithilfe der in der Dissertation entwickelten Algorithmen mit zufrieden stellender Geschwindigkeit lösen lassen.Für Optimierungsprobleme die mithilfe einer Dantzig-Wolfe Dekomposition zerlegt werden können wird gezeigt, dass die polyhedrale Theorie um die partiellen Transversale genutzt werden kann, um nicht identische Subprobleme zu aggregieren.

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.

OpenAccess:
PDF PDF (PDFA)
(additional files)