DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2018.11

A Computational Investigation on the Strength of Dantzig-Wolfe Reformulations

Authors: Michael Bastubbe, Marco E. Lübbecke, and Jonas T. Witt

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

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.

Cite as

Michael Bastubbe, Marco E. Lübbecke, and Jonas T. Witt. A Computational Investigation on the Strength of Dantzig-Wolfe Reformulations. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 11:1-11:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bastubbe_et_al:LIPIcs.SEA.2018.11,
  author =	{Bastubbe, Michael and L\"{u}bbecke, Marco E. and Witt, Jonas T.},
  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 =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.11},
  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}
}

Search Results

Documents authored by Witt, Jonas T.

A Computational Investigation on the Strength of Dantzig-Wolfe Reformulations

Abstract

Cite as

Thanks for your feedback!

Could not send message