Solving the uncapacitated facility location problem with semi-Lagrangian relaxation

C. Beltran-Royo (cesar.beltranurjc.es)
J.-Ph. Vial (jpvialordecsys.com)
A. Alonso-Ayuso (antonio.alonsourjc.es)

Abstract: 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.

Keywords: Lagrangian relaxation, combinatorial optimization, uncapacitated facility location (UFL) problem

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (0-1 Programming )

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Statistics and Operations Research, Rey Juan Carlos University, Mostoles, Madrid, Spain, February, 2007

Download: [PDF]

Entry Submitted: 02/28/2007
Entry Accepted: 02/28/2007
Entry Last Modified: 03/01/2007

Modify/Update this entry