DROPS

Document

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

Authors: George Nemhauser, Mike Hewitt, and Martin Savelsbergh

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

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.

Cite as

George Nemhauser, Mike Hewitt, and Martin Savelsbergh. Using Branch-and-Price to Find High Quality Solutions Quickly. In Models and Algorithms for Optimization in Logistics. Dagstuhl Seminar Proceedings, Volume 9261, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{nemhauser_et_al:DagSemProc.09261.33,
  author =	{Nemhauser, George and Hewitt, Mike and Savelsbergh, Martin},
  title =	{{Using Branch-and-Price to Find High Quality Solutions Quickly}},
  booktitle =	{Models and Algorithms for Optimization in Logistics},
  pages =	{1--2},
  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/entities/document/10.4230/DagSemProc.09261.33},
  URN =		{urn:nbn:de:0030-drops-21681},
  doi =		{10.4230/DagSemProc.09261.33},
  annote =	{Keywords: Column generation, branch-and-price, mixed-integer programming, inventory routing}
}

Search Results

Documents authored by Savelsbergh, Martin

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

Abstract

Cite as

Thanks for your feedback!

Could not send message