Near-optimal solutions to large scale facility location problems

Francisco Barahona (barahonus.ibm.com)
Fabian Chudak (chudakcl.com)

Abstract: We investigate the solution of large scale instances of the capacitated and uncapacitated facility location problems. Let n be the number of customers and m the number of potential facility sites. For the uncapacitated case we solved instances of size m x n=3000 x 3000; for the capacitated case the largest instances were 1000 x 1000. We use heuristics that produce a feasible integer solution and use a Lagrangian relaxation to obtain a lower bound on the optimal value. In particular, we present new heuristics whose gap from optimality was generally below 1%. The heuristics combine the volume algorithm and randomized rounding. For the uncapacitated facility location problem, our computational experiments show that our heuristic compares favorably against DUALOC.

Keywords: Volume algorithm, randomized rounding, facility location

Category 1: Applications -- Science and Engineering (Other )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Category 3: Other Topics (Other )

Citation: IBM Research Report RC21606, 1999

Download: [Postscript]

Entry Submitted: 02/02/2001
Entry Accepted: 02/02/2001
Entry Last Modified: 02/02/2001

Modify/Update this entry