A method for solving to optimality uncapacitated location problems. (English) Zbl 0707.90060

Summary: We develop a method for solving to optimality a general 0-1 formulation for uncapacitated location problems. This is a 3-stage method that solves large problems in reasonable computing times.
The 3-stage method is composed of a primal-dual algorithm, a subgradient optimization to solve a Lagrangean dual and a branch-and-bound algorithm. It has a hierarchical structure, with a given stage being activated only if the optimal solution could not be identified in the preceding stage.
The proposed method was used in the solution of three well-known uncapacitated location problems; the simple plant location problem, the p-median problem and the fixed-charge p-median problem. Computational results are given for problems of up to the size 200 customers\(\times 200\) potential facility sites.


90B80 Discrete location and assignment
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C06 Large-scale problems in mathematical programming
90C09 Boolean programming
Full Text: DOI


[1] J.E. Beasley, A note on solving largep-median problems, Eur. J. Oper. Res. 21 (1985) 270. · Zbl 0569.90021
[2] O. Bilde and J. Krarup, Sharp lower bounds and efficient algorithms for the plant location problem, Ann. Disc. Math. 1 (1977) 79. · Zbl 0364.90068
[3] T.B. Boffey and J. Karkazis,p-medians and multi-medians, J. Oper. Res. Soc. 35 (1984) 57. · Zbl 0526.90036
[4] N. Christofides,Graph Theory: An Algorithmic Approach (Academic Press, 1975).
[5] N. Christofides and J.E. Beasley, A tree search algorithm for thep-median problem, Eur. J. Oper. Res. 10 (1982) 196. · Zbl 0481.90020
[6] G. Cornuejols, M.L. Fisher and G.L. Nemhauser, Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms, Man. Sci. 23 (1977) 789. · Zbl 0361.90034
[7] M.A. Efroymson and T.L. Ray, A branch-bound algorithm for plant location, Oper. Res. 14 (1966) 361.
[8] S. Eilon and R.D. Galvão, Single and double vertex substitution in heuristic procedures for thep-median problem, Man. Sci. 24 (1978) 1763.
[9] A.M. El-Shaieb, A new algorithm for locating sources among destinations, Man. Sci. 20 (1973) 221.
[10] D. Erlenkotter, A dual-based procedure for uncapacitated facility location, Oper. Res. 26 (1978) 992. · Zbl 0422.90053
[11] M.L. Fisher, The Lagrangean relaxation method for solving integer programming problems, Man. Sci. 27 (1981) 1. · Zbl 0539.90079
[12] R.D. Galvão, A dual-bounded algorithm for thep-median problem, Oper. Res. 28 (1980) 1112. · Zbl 0451.90040
[13] R.D. Galvão, L.A. Raggi and M.W. Poubel, Métodos de substituição de vértices na solução de problemas de localizaçào em redes (Vertex substitution methods for network location problems), in:Avances en Investigación Operativa (Yanina, Buenos Aires, 1986) p. 151.
[14] S.L. Hakimi, Optimal location of switching centers and the absolute centers and medians of a graph, Oper. Res. 12 (1964) 450. · Zbl 0123.00305
[15] S.L. Hakimi, Optimum distribution of switching centers in a communication network and some related graph theoretic problems, Oper. Res. 13 (1965) 462. · Zbl 0135.20501
[16] P. Hanjoul and D. Peeters, A comparison of two dual-based procedures for solving thep-median problem, Eur. J. Oper. Res. 20 (1985) 387. · Zbl 0565.90011
[17] M. Held, P. Wolfe and H.P. Crowder, Validation of subgradient optimization, Math. Prog. 6 (1974) 62. · Zbl 0284.90057
[18] P. Jarvinen, J. Rajala and H. Sinervo, A branch-and-bound algorithm for seeking thep-median, Oper. Res. 20 (1972) 173. · Zbl 0232.90035
[19] R.L. Karg and G.L. Thompson, A heuristic approach to solving travelling salesman problems, Man. Sci. 10 (1964) 225.
[20] P. Krolak, W. Felts and G. Marble, A man-machine approach toward solving the traveling salesman problems, Comm. of the ACM 14 (1971) 327. · Zbl 0217.27302
[21] A.A. Kuehn and M.J. Hamburger. A heuristic program for locating warehouses, Man. Sci. 9 (1963) 643.
[22] R.S. Laundy, A tree search algorithm for the multi-commodity location problem, Eur. J. Oper. Res. 20 (1985) 344. · Zbl 0565.90012
[23] P. Mirchandani, A. Oudjit and R.T. Wong, ”Multidimensional” extensions and a nested dual approach for them-median problem, Eur. J. Oper. Res. 21 (1985) 121. · Zbl 0587.90037
[24] S.C. Narula, U.I. Ogbu and H.M. Samuelsson, An algorithm for thep-median problem, Oper. Res. 25 (1977) 709. · Zbl 0372.90096
[25] B.T. Poljak, A general method for solving extremum problems, Soviet Mathematics Dokl. 8 (1967) 593. · Zbl 0147.35302
[26] M.B. Teitz and P. Bart, Heuristic methods for estimating the generalized vertex median of a weighted graph, Oper. Res. 16 (1968) 955. · Zbl 0165.22804
[27] R.A. Whitaker, A fast algorithm for the greedy interchange for large-scale clustering and median location problems, INFOR, Canadian J. Oper. Res. and Info. Proc. 21 (1983) 95. · Zbl 0527.90017
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.