Article ID: | iaor20091069 |
Country: | Netherlands |
Volume: | 159 |
Issue: | 1 |
Start Page Number: | 355 |
End Page Number: | 371 |
Publication Date: | Mar 2008 |
Journal: | Annals of Operations Research |
Authors: | Krumke Sven O., Westphal Stephan |
Keywords: | scheduling |
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.