5 Search Results for "Lübbecke, Marco"

Volume

OASIcs, Volume 14

10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)

ATMOS 2010, September 9, 2010, Liverpool, United Kingdom

Editors: Thomas Erlebach and Marco Lübbecke

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-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
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2010
OASIcs, Volume 14, ATMOS'10, Complete Volume

Authors: Thomas Erlebach and Marco Lübbecke

Published in: OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)

Abstract
OASIcs, Volume 14, ATMOS'10, Complete Volume
Cite as

10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Proceedings{erlebach_et_al:OASIcs.ATMOS.2010,
  title =	{{OASIcs, Volume 14, ATMOS'10, Complete Volume}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{14},
  editor =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010},
  URN =		{urn:nbn:de:0030-drops-35767},
  doi =		{10.4230/OASIcs.ATMOS.2010},
  annote =	{Keywords: Analysis of Algorithms and Problem Complexity, Optimization, Graph Theory, Applications}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2010.i
Frontmatter, Table of Contents, Preface, Organization

Authors: Thomas Erlebach and Marco Lübbecke

Published in: OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)

Abstract
Titlepage, Table of Contents, Preface, Organization.
Cite as

10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. i-ix, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:OASIcs.ATMOS.2010.i,
  author =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  title =	{{Frontmatter, Table of Contents, Preface, Organization}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{i--ix},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.i},
  URN =		{urn:nbn:de:0030-drops-27584},
  doi =		{10.4230/OASIcs.ATMOS.2010.i},
  annote =	{Keywords: Titlepage, Table of Contents, Preface, Organization}
}
Document
DOI: 10.4230/DagSemProc.09261.26
Sequencing and Scheduling in Coil Coating with Shuttles

Authors: Wiebke Höhn, Felix G. König, Marco E. Lübbecke, and Rolf H. Möhring

Published in: Dagstuhl Seminar Proceedings, Volume 9261, Models and Algorithms for Optimization in Logistics (2009)

Abstract
Applying combinatorial optimization in real life yields cost savings delighting the industry. Beyond that, at the core of some applications also lies a pretty (sub)problem rejoicing the mathematician. In our application coils of sheet metal are coated with k layers out of hundreds of colors. Coils are stapled together to run through k coaters, and non-productive time occurs e.g. when the color in a coater needs to be changed. Some coaters have two parallel tanks, enabling either parallel colors or cleaning of one tank during production. We present our sequencing and scheduling scheme in use at the plant today, lower bounds proving solution quality, and problems in the edge-wise union of interval graphs as a pretty mathematical subproblem.
Cite as

Wiebke Höhn, Felix G. König, Marco E. Lübbecke, and Rolf H. Möhring. Sequencing and Scheduling in Coil Coating with Shuttles. In Models and Algorithms for Optimization in Logistics. Dagstuhl Seminar Proceedings, Volume 9261, pp. 1-29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{hohn_et_al:DagSemProc.09261.26,
  author =	{H\"{o}hn, Wiebke and K\"{o}nig, Felix G. and L\"{u}bbecke, Marco E. and M\"{o}hring, Rolf H.},
  title =	{{Sequencing and Scheduling in Coil Coating with Shuttles}},
  booktitle =	{Models and Algorithms for Optimization in Logistics},
  pages =	{1--29},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9261},
  editor =	{Cynthia Barnhart and Uwe Clausen and Ulrich Lauther and Rolf H. M\"{o}hring},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09261.26},
  URN =		{urn:nbn:de:0030-drops-21654},
  doi =		{10.4230/DagSemProc.09261.26},
  annote =	{Keywords: Sequencing, scheduling, coil coating, mutli-interval graphs, heuristics, branch and price}
}
  • Refine by Author
  • 2 Erlebach, Thomas
  • 2 Lübbecke, Marco
  • 2 Lübbecke, Marco E.
  • 1 Bastubbe, Michael
  • 1 Höhn, Wiebke
  • Show More...

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

  • Refine by Keyword
  • 1 Analysis of Algorithms and Problem Complexity, Optimization, Graph Theory, Applications
  • 1 Dantzig-Wolfe reformulation
  • 1 Lagrangean relaxation
  • 1 Organization
  • 1 Preface
  • Show More...

  • Refine by Type
  • 4 document
  • 1 volume

  • Refine by Publication Year
  • 2 2010
  • 1 2009
  • 1 2012
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact