2 Search Results for "Wolfe, Michael"


Document
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-dev.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}
}
Document
Loop Parallelization (Dagstuhl Seminar 9616)

Authors: Christian Lengauer, Lothar Thiele, Michael Wolfe, and Hans Zima

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

Christian Lengauer, Lothar Thiele, Michael Wolfe, and Hans Zima. Loop Parallelization (Dagstuhl Seminar 9616). Dagstuhl Seminar Report 142, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1996)


Copy BibTex To Clipboard

@TechReport{lengauer_et_al:DagSemRep.142,
  author =	{Lengauer, Christian and Thiele, Lothar and Wolfe, Michael and Zima, Hans},
  title =	{{Loop Parallelization (Dagstuhl Seminar 9616)}},
  pages =	{1--22},
  ISSN =	{1619-0203},
  year =	{1996},
  type = 	{Dagstuhl Seminar Report},
  number =	{142},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.142},
  URN =		{urn:nbn:de:0030-drops-150292},
  doi =		{10.4230/DagSemRep.142},
}
  • Refine by Author
  • 1 Bastubbe, Michael
  • 1 Lengauer, Christian
  • 1 Lübbecke, Marco E.
  • 1 Thiele, Lothar
  • 1 Witt, Jonas T.
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Integer programming

  • Refine by Keyword
  • 1 Dantzig-Wolfe reformulation
  • 1 Lagrangean relaxation
  • 1 column generation
  • 1 hierarchy of relaxations
  • 1 partial convexification
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 1996
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail