Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 1140.90442
Barahona, Francisco; Chudak, Fabián A.
Near-optimal solutions to large-scale facility location problems.
(English)
[J] Discrete Optim. 2, No. 1, 35-50 (2005). ISSN 1572-5286

Summary: 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\times n=3000\times 3000$; for the capacitated case the largest instances were $1000\times 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.
MSC 2000:
*90B85 Continuous location
90C59 Approximation methods and heuristics

Keywords: Volume algorithm; Randomized rounding; Facility location

Highlights
Master Server