h1

% IMPORTANT: The following is UTF-8 encoded.  This means that in the presence
% of non-ASCII characters, it will not work with BibTeX 0.99 or older.
% Instead, you should use an up-to-date BibTeX implementation like “bibtex8” or
% “biber”.

@PHDTHESIS{Witt:780278,
      author       = {Witt, Jonas Timon},
      othercontributors = {Lübbecke, Marco and Koster, Arie Marinus and Desaulniers,
                          Guy},
      title        = {{P}olyhedral aspects of {D}antzig-{W}olfe reformulation},
      school       = {RWTH Aachen University},
      type         = {Dissertation},
      address      = {Aachen},
      reportid     = {RWTH-2020-00547},
      pages        = {1 Online-Ressource (xvii, 213 Seiten) : Illustrationen},
      year         = {2019},
      note         = {Veröffentlicht auf dem Publikationsserver der RWTH Aachen
                      University 2020; Dissertation, RWTH Aachen University, 2019},
      abstract     = {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.},
      cin          = {813310 / 113320 / 110000},
      ddc          = {510},
      cid          = {$I:(DE-82)813310_20140620$ / $I:(DE-82)113320_20140620$ /
                      $I:(DE-82)110000_20140620$},
      typ          = {PUB:(DE-HGF)11},
      doi          = {10.18154/RWTH-2020-00547},
      url          = {https://publications.rwth-aachen.de/record/780278},
}