License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-21905
URL: http://drops.dagstuhl.de/opus/volltexte/2009/2190/

Helmberg, Christoph

Network Models with Convex Cost Structure like Bundle Methods

pdf-format:
Dokument 1.pdf (174 KB)


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:DSP:2009:2190,
  author =	{Christoph Helmberg},
  title =	{Network Models with Convex Cost Structure like Bundle Methods},
  booktitle =	{Models and Algorithms for Optimization in Logistics},
  year =	{2009},
  editor =	{Cynthia Barnhart and Uwe Clausen and Ulrich Lauther and Rolf H. M{\"o}hring},
  number =	{09261},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2190},
  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
Seminar: 09261 - Models and Algorithms for Optimization in Logistics
Issue date: 2009
Date of publication: 02.10.2009


DROPS-Home | Fulltext Search | Imprint Published by LZI