The semi-Lagrangian Relaxation (SLR) method has been introduced in Beltran et al. (2006) to solve the p-median problem. In this paper we apply the method to the Uncapacitated Facility Location (UFL) problem. We perform computational experiments on two main collections of UFL problems with unknown optimal values. On one collection, we manage to solve to optimality 16 out of the 18 instances. On the second collection we solve 2 out of 18 instances and improve the Lagrangian lower bound. In this way, we prove that the Hybrid Multistart heuristic of Resende et al. (2006) provides near optimal solutions.
Citation
Statistics and Operations Research, Rey Juan Carlos University, Mostoles, Madrid, Spain, February, 2007