Polyhedral aspects of Dantzig-Wolfe reformulation

Witt, Jonas Timon; Koster, Arie Marinus; Lübbecke, Marco; Desaulniers, Guy

doi:10.18154/RWTH-2020-00547

Polyhedral aspects of Dantzig-Wolfe reformulation = Polyedrische Aspekte von Dantzig-Wolfe Reformulierung

Witt, Jonas Timon^RWTH*

2019 & 2020

Verantwortlichkeitsangabevon Master of Science Jonas T. Witt

ImpressumAachen 2019

Umfang1 Online-Ressource (xvii, 213 Seiten) : Illustrationen

Dissertation, RWTH Aachen University, 2019

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2020

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Lübbecke, Marco (Thesis advisor)^RWTH* ; Koster, Arie Marinus (Thesis advisor)^RWTH* ; Desaulniers, Guy (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2019-11-29

Online
DOI: 10.18154/RWTH-2020-00547
URL: https://publications.rwth-aachen.de/record/780278/files/780278.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Dantzig-Wolfe decomposition (frei) ; Dantzig-Wolfe reformulation (frei) ; branch-and-price (frei) ; column generation (frei) ; cutting planes (frei) ; integer programming (frei) ; polyhedra (frei) ; stable set problem (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

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.

Although Dantzig-Wolfe reformulation for integer programs has practically proven to yield strong relaxations in various applications, there is only a poor theoretical understanding of Dantzig-Wolfe reformulation in general. This thesis addresses this issue and contributes to a better understanding of Dantzig-Wolfe reformulation and the underlying polyhedral theory. We investigate all (exponentially many) Dantzig-Wolfe reformulations for a given integer program both theoretically (for particular problem classes) and computationally (for small models). For the stable set problem we characterize Dantzig-Wolfe reformulations yielding particularly strong and weak relaxations. These findings also give new insights on the stable set polytope and (partially) extend to related problems like the matching and the set packing problem. Besides, we computationally evaluate the dual bounds obtained from all Dantzig-Wolfe reformulations for small models of different problem classes. We observe that only few distinct dual bounds occur and demonstrate that some constraints have a specifically high influence on the dual bound in these Dantzig-Wolfe reformulations. Furthermore, we investigate whether Dantzig-Wolfe reformulations proposed in the literature (for particular problem classes) can be further strengthened with cutting planes from the initial integer program. In a comprehensive computational study we demonstrate that generic classes of cutting planes only rarely strengthen these Dantzig-Wolfe reformulations. Motivated by this, we prove that whole classes of generic cutting planes are already obtained by some Dantzig-Wolfe reformulations from the literature. In addition, we introduce a novel class of cutting planes, which is strongly related to classical Benders’ cuts. These cutting planes strengthen some of the considered Dantzig-Wolfe reformulations from the literature. With this work we shed more light on the polyhedral aspects of Dantzig-Wolfe reformulation and contribute to a better understanding of the strength of Dantzig-Wolfe reformulation in general.

OpenAccess:
PDF
(additional files)