Article ID: | iaor200971088 |
Country: | Germany |
Volume: | 167 |
Issue: | 1 |
Start Page Number: | 209 |
End Page Number: | 251 |
Publication Date: | Mar 2009 |
Journal: | Annals of Operations Research |
Authors: | Righini Giovanni, Ceselli Alberto, Liberatore Federico |
Keywords: | networks |
The purpose of this paper is to illustrate a general framework for network location problems, based on column generation and branch-and-price. In particular we consider capacitated network location problems with single-source constraints. We consider several different network location models, by combining cardinality constraints, fixed costs, concentrator restrictions and regional constraints. Our general branch-and-price-based approach can be seen as a natural counterpart of the branch-and-cut-based commercial ILP solvers, with the advantage of exploiting the tightness of the lower bound provided by the set partitioning reformulation of network location problems. Branch-and-price and branch-and-cut are compared through an extensive set of experimental tests.