Advanced Search

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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]