Polyhedral aspects of Dantzig-Wolfe reformulation

• Polyedrische Aspekte von Dantzig-Wolfe Reformulierung

Witt, Jonas Timon; Lübbecke, Marco (Thesis advisor); Koster, Arie Marinus (Thesis advisor); Desaulniers, Guy (Thesis advisor)

Aachen (2019, 2020)
Doktorarbeit

Dissertation, RWTH Aachen University, 2019

Kurzfassung

Obwohl Dantzig-Wolfe Reformulierung für ganzzahlige Programme in der Praxis gezeigt hat, starke Relaxationen in verschiedenen Anwendungen zu liefern, ist das theoretische Verständnis von Dantzig-Wolfe Reformulierung im Allgemeinen relativ gering. Die vorliegende Arbeit setzt sich mit dieser Problematik auseinander und trägt zu einem besseren Verständnis von Dantzig-Wolfe Reformulierung und der zugrundeliegenden polyedrischen Theorie bei. Wir untersuchen alle (exponentiell vielen) Dantzig-Wolfe Reformulierungen für ein gegebenes ganzzahliges Programm sowohl theoretisch (für spezielle Probemklassen) als auch rechnerisch (für keine Modelle). Für das Stabile-Mengen-Problem charakterisieren wir Dantzig-Wolfe Reformulierungen, die besonders starke bzw. besonders schwache Relaxationen liefern. Diese Ergebnisse geben außerdem neue Erkentnisse über das Stabile-Mengen-Polytop und lassen sich (teilweise) auf verwandte Probleme wie das Matching- oder Mengenpackungsproblem erweitern. Außerdem werten wir rechnerisch duale Schranken von allenDantzig-Wolfe Reformulierungen für kleine Modelle verschiedener Problemklassen aus. Dabei beobachten wir, dass nur wenige verschiedene duale Schranken auftreten, und zeigen, dass manche Nebenbedingungen eine besonders hohen Einfluss auf die duale Schranke in diesen Dantzig-Wolfe Reformulierungen haben. Desweiteren wird untersucht, ob Dantzig-Wolfe Reformulierungen, die in der Literatur (für bestimmte Problemklassen) vorgeschlagen wurden, weiter mit Schnittebenen aus dem ursprünglichen ganzzahligen Programm verstärkt werden können. In einer umfassenden Rechenstudie wird von uns demonstriert, dass generische Klassen von Schnittebenen diese Dantzig-Wolfe Reformulierungen kaum verstärken. Motiviert durch diese Ergebnisse zeigen wir, dass ganze Klassen von generischen Schnittebenen bereits durch manche Dantzig-Wolfe Reformulierungen aus der Literatur erhalten werden. Zusätzlich führen wir eine neue Klasse von Schnittebenen ein, die in enger Verbindung zu klassischen Benders Schnittebenen stehen. Diese Schnittebenen verstärken manche der betrachteten Dantzig-Wolfe Reformulierungen aus der Literatur. In der vorliegenden Arbeit beleuchten wir besonders stark die polyedrischen Aspekte von Dantzig-Wolfe Reformulierung und tragen zu einem besseren allgemeinen Verständnis der Stärke von Dantzig-WolfeReformulierung bei.

Einrichtungen

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