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.

## Citation

IBM Research Report RC21606, 1999

## Article

View Near-optimal solutions to large scale facility location problems