Branch and Price for Large‐Scale Capacitated Hub Location Problems with Single Assignment

Branch and Price for Large‐Scale Capacitated Hub Location Problems with Single Assignment

0.00 Avg rating0 Votes
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: , ,
Keywords: programming: mathematical
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.