Article ID: | iaor20112496 |
Volume: | 23 |
Issue: | 1 |
Start Page Number: | 41 |
End Page Number: | 55 |
Publication Date: | Dec 2011 |
Journal: | INFORMS Journal on Computing |
Authors: | Fernndez Elena, Contreras Ivan, Daz Juan A |
Keywords: | programming: mathematical |
This paper presents a branch‐and‐price algorithm for the capacitated hub location problem with single assignment, in which Lagrangean relaxation is used to obtain tight lower bounds of the restricted master problem. A lower bound that is valid at any stage of the column generation algorithm is proposed. The process to obtain this valid lower bound is combined with a constrained stabilization method that results in a considerable improvement on the overall efficiency of the solution algorithm. Numerical results on a battery of benchmark instances of up to 200 nodes are reported. These seem to be the largest instances that have been solved to optimality for this problem.