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)
Dissertation / PhD Thesis

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.