License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2018.11
URN: urn:nbn:de:0030-drops-89464
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8946/
Go to the corresponding LIPIcs Volume Portal

Bastubbe, Michael ; Lübbecke, Marco E. ; Witt, Jonas T.

A Computational Investigation on the Strength of Dantzig-Wolfe Reformulations

pdf-format:
LIPIcs-SEA-2018-11.pdf (0.9 MB)

Abstract

In Dantzig-Wolfe reformulation of an integer program one convexifies a subset of the constraints, leading to potentially stronger dual bounds from the respective linear programming relaxation. As the subset can be chosen arbitrarily, this includes the trivial cases of convexifying no and all constraints, resulting in a weakest and strongest reformulation, respectively. Our computational study aims at better understanding of what happens in between these extremes. For a collection of integer programs with few constraints we compute, optimally solve, and evaluate the relaxations of all possible (exponentially many) Dantzig-Wolfe reformulations (with mild extensions to larger models from the MIPLIBs). We observe that only a tiny number of different dual bounds actually occur and that only a few inclusion-wise minimal representatives exist for each. This aligns with considerably different impacts of individual constraints on the strengthening the relaxation, some of which have almost no influence. In contrast, types of constraints that are convexified in textbook reformulations have a larger effect. We relate our experiments to what could be called a hierarchy of Dantzig-Wolfe reformulations.

BibTeX - Entry

@InProceedings{bastubbe_et_al:LIPIcs:2018:8946,
  author =	{Michael Bastubbe and Marco E. L{\"u}bbecke and Jonas T. Witt},
  title =	{{A Computational Investigation on the Strength of Dantzig-Wolfe Reformulations}},
  booktitle =	{17th International Symposium on Experimental Algorithms  (SEA 2018)},
  pages =	{11:1--11:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{Gianlorenzo D'Angelo},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8946},
  URN =		{urn:nbn:de:0030-drops-89464},
  doi =		{10.4230/LIPIcs.SEA.2018.11},
  annote =	{Keywords: Dantzig-Wolfe reformulation, strength of reformulations, Lagrangean relaxation, partial convexification, column generation, hierarchy of relaxations}
}

Keywords: Dantzig-Wolfe reformulation, strength of reformulations, Lagrangean relaxation, partial convexification, column generation, hierarchy of relaxations
Collection: 17th International Symposium on Experimental Algorithms (SEA 2018)
Issue Date: 2018
Date of publication: 19.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI