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.
A computational evaluation of a general branch-and-price framework for capacitated network location problems / A. Ceselli, F. Liberatore, G. Righini. - In: ANNALS OF OPERATIONS RESEARCH. - ISSN 0254-5330. - 167:1(2009 Mar), pp. 209-251.
A computational evaluation of a general branch-and-price framework for capacitated network location problems
A. CeselliPrimo
;G. RighiniUltimo
2009
Abstract
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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.