A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem. (English) Zbl 0967.90068

Summary: We compare heuristics based on Lagrangean and surrogate relaxations of the Maximal Covering Location Problem (MCLP). The Lagrangean relaxation of MCLP used in this paper has the integrality property and the surrogate relaxed problem we solve is the LP relaxation of the original 0-1 knapsack problem. The heuristics were compared using 331 test problems available in the literature, corresponding to networks ranging from 55 to 900 vertices. The gaps obtained with both heuristics were very low and did not differ substantially among themselves for the several problem sets used, in accordance with theoretical results reviewed in the paper. When the initial set of multipliers was determined using a valid bound for MCLP the computing times did not differ significantly between the Lagrangean and surrogate heuristics.


90B80 Discrete location and assignment


Full Text: DOI


[1] Almiñana, M.; Pastor, J.T., An adaptation of SH heuristic to the location set covering problem, European journal of operational research, 100, 586-593, (1997) · Zbl 0920.90087
[2] Beasley, J.E., OR-library: distributing test problems by electronic mail, Journal of the operational research society, 41, 1069-1072, (1990)
[3] Beasley, J.E., An algorithm for the set covering problem, European journal of operational research, 31, 85-93, (1987) · Zbl 0679.90039
[4] T.B. Boffey, C.S. Narula, Multiobjective covering and routing problems, in: M. Karwan, J. Spronk and J. Wallenius (Eds.), Essays in Decision Making: A Volume in Honor of Stanley Zionts, Springer, Berlin, 1997, pp. 342-370. · Zbl 0893.90115
[5] Chung, C.H., Recent applications of the maximal covering location problem (MCLP) model, Journal of the operational research society, 37, 735-746, (1986) · Zbl 0601.90043
[6] Church, R.L.; ReVelle, C.S., The maximal covering location problem, Papers of the regional science association, 32, 101-118, (1974)
[7] Current, J.; O’Kelly, M., Locating emergency warning sirens, Decision sciences, 23, 221-234, (1992)
[8] Daskin, M.S.; Jones, P.C.; Lowe, T.J., Rationalizing tool selection in a flexible manufacturing system for sheet metal products, Operations research, 38, 1104-1115, (1990) · Zbl 0723.90034
[9] Downs, B.T.; Camm, J.D., An exact algorithm for the maximal covering location problem, Naval research logistics quarterly, 43, 435-461, (1996) · Zbl 0846.90076
[10] Duszinski, K.; Waluckiewicz, S., A fast algorithm for the linear multiple choice knapsack problem, Operational research letters, 3, 205-209, (1984)
[11] Duszinski, K.; Waluckiewicz, S., Exact methods for the knapsack problem and its generalizations, European journal of operational research, 28, 3-21, (1987)
[12] Dwyer, F.R.; Evans, J.R., A branch and bound algorithm for the List selection problem in direct mail advertising, Management science, 27, 658-667, (1981)
[13] Eaton, D.; Hector, M.; Sanchez, V.; Latingua, R.; Morgan, J., Determining ambulance deployment in santo domingo, dominican republic, Journal of the operational research society, 37, 113-126, (1986)
[14] Eilon, S.; Galvão, R.D., Single and double vertex substitution in heuristic procedures for the p-Median problem, Management science, 24, 1763-1766, (1978) · Zbl 0491.90036
[15] Galvão, R.D.; ReVelle, C.S., A Lagrangean heuristic for the maximal covering location problem, European journal of operational research, 88, 114-123, (1996) · Zbl 0913.90200
[16] M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W.H. Freeman and Co., San Francisco, 1979. · Zbl 0411.68039
[17] Geoffrion, A.M., Lagrangean relaxation for integer programming, Mathematical programming study, 2, 82-114, (1974) · Zbl 0395.90056
[18] Glover, F., A multiphase-dual algorithm for the zero – one integer programming problem, Operations research, 13, 879-919, (1965) · Zbl 0163.41301
[19] Glover, F., Surrogate constraints, Operations research, 16, 741-749, (1968) · Zbl 0165.22602
[20] Glover, F., Surrogate constraint duality in mathematical programming, Operations research, 23, 434-451, (1975) · Zbl 0314.90093
[21] Greenberg, H.J.; Pierskalla, W.P., Surrogate mathematical programming, operations research, 18, 924-939, (1970) · Zbl 0232.90059
[22] Greenberg, H.J.; Pierskalla, W.P., Quasi-conjugate functions and surrogate duality, Cahiers du centre d’études de recherche opérationnelle, 15, 437-448, (1973) · Zbl 0276.90051
[23] Hougland, E.S.; Stephens, N.T., Air pollutant monitor siting by analytical techniques, Journal of the air polution control association, 26, 52-53, (1976)
[24] Karwan, M.H.; Rardin, R.L., Some relationships between Lagrangian and surrogate duality in integer programming, Mathematical programming, 17, 320-334, (1979) · Zbl 0421.90056
[25] Lorena, L.A.N.; Lopes, F.B., A surrogate heuristic for set covering problems, European journal of operational research, 79, 138-150, (1994) · Zbl 0813.90096
[26] Lorena, L.A.N.; Narciso, M.G., Relaxation heuristics for a generalized assignment problem, European journal of operational research, 91, 600-610, (1996) · Zbl 0924.90119
[27] Pastor, J.T., Bicriterion programs and managerial locations: application to the banking sector, Journal of the operational research society, 45, 1351-1362, (1994) · Zbl 0814.90069
[28] R. Swain, A decomposition algorithm for a class of facility location problems, Ph.D. Thesis, Cornell University, Ithaca, NY, 1971
[29] G.R. Walsh, Methods of Optimization, Wiley, London, 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.