Near-optimal solutions to large-scale facility location problems. (English) Zbl 1140.90442

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.


90B85 Continuous location
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI


[1] Aardal, K., Capacitated facility locationseparation algorithms and computational experience, Math. Programming, 81, 149-175 (1998) · Zbl 0919.90096
[2] Ahn, S.; Cooper, C.; Cornuéjols, G.; Frieze, A. M., Probabilistic analysis of a relaxation for the \(k\)-median problem, Math. Oper. Res., 13, 1-31 (1988) · Zbl 0653.90049
[3] Balinski, M. L., Integer programmingmethods, uses, computation, Management Sci., 12, 3, 253-313 (1965) · Zbl 0129.12004
[4] Barahona, F.; Anbil, R., The volume algorithmproducing primal solutions with a subgradient method, Math. Programming, 87, 385-399 (2000) · Zbl 0961.90058
[6] Chudak, F. A., Improved approximation algorithms for uncapacitated facility location, (Proceedings of the 6th IPCO Conference (1998)), 180-194 · Zbl 0910.90201
[8] Cornuéjols, G.; Nemhauser, G. L.; Wolsey, L. A., The uncapacitated facility location problem, (Mirchandani, P.; Francis, R., Discrete Location Theory (1990), Wiley: Wiley New York), 119-171 · Zbl 0727.90043
[9] Cornuéjols, G.; Sridharan, R.; Thizy, J. M., A comparison of heuristics and relaxations for the capacitated plant location problem, European J. Oper. Res., 50, 280-297 (1991) · Zbl 0734.90046
[10] Erlenkotter, D., A dual-based procedure for uncapacitated facility location, Oper. Res., 26, 992-1009 (1978) · Zbl 0422.90053
[13] Held, M.; Wolfe, P.; Crowder, H. P., Validation of subgradient optimization, Math. Programming, 49, 62-88 (1991) · Zbl 0284.90057
[16] Raghavan, P.; Thompson, C. D., Randomized rounding, Combinatorica, 7, 365-374 (1987) · Zbl 0651.90052
[18] Wolfe, P., A method of conjugate subgradients for minimizing nondifferentiable functions, Math. Programming Study, 3, 145-173 (1975)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.