License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-21681
URL: http://drops.dagstuhl.de/opus/volltexte/2009/2168/
Go to the corresponding Portal


Nemhauser, George ; Hewitt, Mike ; Savelsbergh, Martin

Using Branch-and-Price to Find High Quality Solutions Quickly

pdf-format:
Document 1.pdf (54 KB)


Abstract

We develop an exact solution approach for integer programs that produces high- quality solutions quickly by solving well-chosen restrictions of the problem. Column generation is used both for generating these problem restrictions and for producing bounds on the value of an optimal solution to the problem. Obtaining primal solutions by solving problem restrictions also provides an easy way to search for improved solutions in the neighborhood of the current best solution. The overall approach is parallelized and computational experiments demonstrate its efficacy. An application to inventory routing is presented.

BibTeX - Entry

@InProceedings{nemhauser_et_al:DSP:2009:2168,
  author =	{George Nemhauser and Mike Hewitt and Martin Savelsbergh},
  title =	{Using Branch-and-Price to Find High Quality Solutions Quickly},
  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/2168},
  annote =	{Keywords: Column generation, branch-and-price,  mixed-integer programming, inventory routing}
}

Keywords: Column generation, branch-and-price, mixed-integer programming, inventory routing
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