License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09261.17
URN: urn:nbn:de:0030-drops-21905
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2190/
Go to the corresponding Portal

Helmberg, Christoph

Network Models with Convex Cost Structure like Bundle Methods

pdf-format:
09261.HelmbergChristoph.ExtAbstract.2190.pdf (0.2 MB)

Abstract

For three rather diverse applications (truck scheduling for inter warehouse logistics, university-course timetabling, operational train timetabling) that contain integer multi-commodity flow as a major modeling element we present a computational comparison between a bundle and a full linear programming (LP) approach for solving the basic relaxations. In all three cases computing the optimal solutions with LP standard solvers is computationally very time consuming if not impractical due to high memory consumption while bundle methods produce solutions of sufficient but low accuracy in acceptable time.
The rounding heuristics generate comparable results for the exact and the approximate solutions, so this entails no loss in quality of the final solution. Furthermore, bundle methods facilitate the use of nonlinear convex cost functions. In practice this not only improves the quality of the relaxation but even seems to speed up convergence of the method.

BibTeX - Entry

@InProceedings{helmberg:DagSemProc.09261.17,
  author =	{Helmberg, Christoph},
  title =	{{Network Models with Convex Cost Structure like Bundle Methods}},
  booktitle =	{Models and Algorithms for Optimization in Logistics},
  pages =	{1--8},
  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.dagstuhl.de/opus/volltexte/2009/2190},
  URN =		{urn:nbn:de:0030-drops-21905},
  doi =		{10.4230/DagSemProc.09261.17},
  annote =	{Keywords: Lagrangian decomposition, large scale convex optimization, bundle methods, integer multi-commodity flow}
}

Keywords: Lagrangian decomposition, large scale convex optimization, bundle methods, integer multi-commodity flow
Collection: 09261 - Models and Algorithms for Optimization in Logistics
Issue Date: 2009
Date of publication: 02.10.2009

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