Citation
Pruning in column generation for service vehicle dispatching. Annals of Operations Research, 159 (1): 355-371, 2008.
Selected
Abstract
Column generation techniques have become a widely used technique to successfully solve large (integer) linear programs. One of the keys to obtaining a practically efficient algorithm is to have a fast method to limit the pricing of new columns to a small set. We study a large scale real-world vehicle dispatching problem with soft time windows which can be modeled as an integer linear program of set partitioning type. We develop a new pruning scheme based on matchings in order to speed up the branch-and-bound enumeration in the column generation process. Computational results on real-world data illustrate the effectiveness of the new pruning scheme.
There is no pdf available for this paper. You might like to try to obtain the original source (see the doi, for example)
doi
The doi for this publication is 10.1007/s10479-007-0275-0 You can link directly to the original paper, via the doi, from here
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@ARTICLE{2008-355-371-SI, author = {S. Westphal and S. O. Krumke},
title = {Pruning in column generation for service vehicle dispatching},
journal = {Annals of Operations Research},
year = {2008},
volume = {159},
pages = {355--371},
number = {1},
note = {Selected},
abstract = {Column generation techniques have become a widely used technique to successfully solve large (integer) linear programs. One of the keys to obtaining a practically efficient algorithm is to have a fast method to limit the pricing of new columns to a small set. We study a large scale real-world vehicle dispatching problem with soft time windows which can be modeled as an integer linear program of set partitioning type. We develop a new pruning scheme based on matchings in order to speed up the branch-and-bound enumeration in the column generation process. Computational results on real-world data illustrate the effectiveness of the new pruning scheme.},
doi = {10.1007/s10479-007-0275-0},
owner = {user},
timestamp = {2012.05.25} }