Branch-and-Price Heuristics: A Case Study on the Vehicle Routing Problem with Time Windows

Emilie Danna () and Claude Pape ()
Additional contact information
Emilie Danna: Georgia Institute of Technology
Claude Pape: ILOG S.A.

Chapter Chapter 4 in Column Generation, 2005, pp 99-129 from Springer

Abstract: Abstract Branch-and-price is a powerful framework to solve hard combinatorial problems. It is an interesting alternative to general purpose mixed integer programming as column generation usually produces at the root node tight lower bounds (when minimizing) that are further improved when branching. Branching also helps to generate integer solutions, however branch-and-price can be quite weak at producing good integer solutions rapidly because the solution of the relaxed master problem is rarely integer-valued. In this paper, we propose a general cooperation scheme between branch-and-price and local search to help branch-and-price finding good integer solutions earlier. This cooperation scheme extends to branch-and-price the use of heuristics in branch-and-bound and it also generalizes three previously known accelerations of branch-and-price. We show on the vehicle routing problem with time windows (Solomon benchmark) that it consistently improves the ability of branch-and-price to generate good integer solutions ea rly while retaining the ability of branch-and-price to produce good lower bounds.

Keywords: Local Search; Mixed Integer Programming; Column Generation; Master Problem; Integer Solution (search for similar items in EconPapers)
Date: 2005
References: Add references at CitEc
Citations: View citations in EconPapers (16)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-0-387-25486-9_4

Ordering information: This item can be ordered from
http://www.springer.com/9780387254869

DOI: 10.1007/0-387-25486-2_4

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().