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)
Doktorarbeit

Dissertation, RWTH Aachen University, 2016

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.

Einrichtungen

• Fachgruppe Mathematik [110000]
• Lehr- und Forschungsgebiet Diskrete Optimierung [113320]
• Lehrstuhl für Operations Research [813310]