h1

000780278 001__ 780278
000780278 005__ 20230408004313.0
000780278 0247_ $$2HBZ$$aHT020343141
000780278 0247_ $$2Laufende Nummer$$a38912
000780278 0247_ $$2datacite_doi$$a10.18154/RWTH-2020-00547
000780278 037__ $$aRWTH-2020-00547
000780278 041__ $$aEnglish
000780278 082__ $$a510
000780278 1001_ $$0P:(DE-82)IDM02532$$aWitt, Jonas Timon$$b0$$urwth
000780278 245__ $$aPolyhedral aspects of Dantzig-Wolfe reformulation$$cvon Master of Science Jonas T. Witt$$honline
000780278 246_3 $$aPolyedrische Aspekte von Dantzig-Wolfe Reformulierung$$yGerman
000780278 260__ $$aAachen$$c2019
000780278 260__ $$c2020
000780278 300__ $$a1 Online-Ressource (xvii, 213 Seiten) : Illustrationen
000780278 3367_ $$02$$2EndNote$$aThesis
000780278 3367_ $$0PUB:(DE-HGF)11$$2PUB:(DE-HGF)$$aDissertation / PhD Thesis$$bphd$$mphd
000780278 3367_ $$2BibTeX$$aPHDTHESIS
000780278 3367_ $$2DRIVER$$adoctoralThesis
000780278 3367_ $$2DataCite$$aOutput Types/Dissertation
000780278 3367_ $$2ORCID$$aDISSERTATION
000780278 500__ $$aVeröffentlicht auf dem Publikationsserver der RWTH Aachen University 2020
000780278 502__ $$aDissertation, RWTH Aachen University, 2019$$bDissertation$$cRWTH Aachen University$$d2019$$gFak01$$o2019-11-29
000780278 5203_ $$aObwohl 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.$$lger
000780278 520__ $$aAlthough 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.$$leng
000780278 588__ $$aDataset connected to Lobid/HBZ
000780278 591__ $$aGermany
000780278 653_7 $$aDantzig-Wolfe decomposition
000780278 653_7 $$aDantzig-Wolfe reformulation
000780278 653_7 $$abranch-and-price
000780278 653_7 $$acolumn generation
000780278 653_7 $$acutting planes
000780278 653_7 $$ainteger programming
000780278 653_7 $$apolyhedra
000780278 653_7 $$astable set problem
000780278 7001_ $$0P:(DE-82)IDM00416$$aLübbecke, Marco$$b1$$eThesis advisor$$urwth
000780278 7001_ $$0P:(DE-82)IDM00097$$aKoster, Arie Marinus$$b2$$eThesis advisor$$urwth
000780278 7001_ $$0P:(DE-82)063258$$aDesaulniers, Guy$$b3$$eThesis advisor
000780278 8564_ $$uhttps://publications.rwth-aachen.de/record/780278/files/780278.pdf$$yOpenAccess
000780278 8564_ $$uhttps://publications.rwth-aachen.de/record/780278/files/780278_source.zip$$yRestricted
000780278 8564_ $$uhttps://publications.rwth-aachen.de/record/780278/files/780278.gif?subformat=icon$$xicon$$yOpenAccess
000780278 8564_ $$uhttps://publications.rwth-aachen.de/record/780278/files/780278.jpg?subformat=icon-1440$$xicon-1440$$yOpenAccess
000780278 8564_ $$uhttps://publications.rwth-aachen.de/record/780278/files/780278.jpg?subformat=icon-180$$xicon-180$$yOpenAccess
000780278 8564_ $$uhttps://publications.rwth-aachen.de/record/780278/files/780278.jpg?subformat=icon-640$$xicon-640$$yOpenAccess
000780278 8564_ $$uhttps://publications.rwth-aachen.de/record/780278/files/780278.jpg?subformat=icon-700$$xicon-700$$yOpenAccess
000780278 909CO $$ooai:publications.rwth-aachen.de:780278$$popenaire$$popen_access$$pVDB$$pdriver$$pdnbdelivery
000780278 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM02532$$aRWTH Aachen$$b0$$kRWTH
000780278 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM00416$$aRWTH Aachen$$b1$$kRWTH
000780278 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM00097$$aRWTH Aachen$$b2$$kRWTH
000780278 9141_ $$y2019
000780278 915__ $$0StatID:(DE-HGF)0510$$2StatID$$aOpenAccess
000780278 9201_ $$0I:(DE-82)813310_20140620$$k813310$$lLehrstuhl für Operations Research$$x0
000780278 9201_ $$0I:(DE-82)113320_20140620$$k113320$$lLehr- und Forschungsgebiet Mathematik (Diskrete Optimierung)$$x1
000780278 9201_ $$0I:(DE-82)110000_20140620$$k110000$$lFachgruppe Mathematik$$x2
000780278 961__ $$c2020-02-13T14:34:18.321419$$x2020-01-13T17:52:17.352915$$z2020-02-13T14:34:18.321419
000780278 9801_ $$aFullTexts
000780278 980__ $$aI:(DE-82)110000_20140620
000780278 980__ $$aI:(DE-82)113320_20140620
000780278 980__ $$aI:(DE-82)813310_20140620
000780278 980__ $$aUNRESTRICTED
000780278 980__ $$aVDB
000780278 980__ $$aphd