Near-optimal solutions to large-scale facility location problems

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×n=3000×3000; for the capacitated case the largest instances were 1000×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.