×

zbMATH — the first resource for mathematics

Double bound method for solving the \(p\)-center location problem. (English) Zbl 1348.90384
Summary: We give a review of existing methods for solving the absolute and vertex restricted \(p\)-center problems on networks and propose a new integer programming formulation, a tightened version of this formulation and a new method based on successive restrictions of the new formulation. A specialization of the new method with two-element restrictions obtains the optimal \(p\)-center solution by solving a series of simple structured integer programs in recognition form. This specialization is called the double bound method. A relaxation of the proposed formulation gives the tightest known lower bound in the literature (obtained earlier by S. Elloumi et al. [INFORMS J. Comput. 16, No. 1, 84–94 (2004; Zbl 1239.90103)]). A polynomial time algorithm is presented to compute this bound. New lower and upper bounds are proposed. Problems from the OR-Library and TSPLIB are solved by the proposed algorithms with up to 3038 nodes. Previous computational results were restricted to networks with at most 1817 nodes.

MSC:
90B80 Discrete location and assignment
05C12 Distance in graphs
Software:
OR-Library; CPLEX; TSPLIB
PDF BibTeX Cite
Full Text: DOI
References:
[1] Elloumi, S.; Labbé, M.; Pochet, Y., A new formulation and resolution method for the p-center problem, INFORMS Journal on Computing, 16, 1, 84-94, (2004) · Zbl 1239.90103
[2] Beasley, JE. OR-LIBRARY. June 2012. URL 〈http://people.brunel.ac.uk/ mastjjb/jeb/info.html〉.
[3] Reinelt, G., TSPLIB—a traveling salesman problem library, ORSA Journal on Computing, 3, 4, 376-384, (1991) · Zbl 0775.90293
[4] Dearing, P.; Francis, R.; Lowe, T., Convex location problems on tree networks, Operations Research, 24, 4, 628-642, (1976) · Zbl 0341.90042
[5] Hakimi, S. L., Optimum locations of switching centers and the absolute centers and medians of a graph, Operations Research, 12, 3, 450-459, (1964) · Zbl 0123.00305
[6] Minieka, E., The m-center problem, SIAM Review, 12, 1, 138-139, (1970) · Zbl 0193.24204
[7] Kariv, O.; Hakimi, S. L., An algorithmic approach to network location problems. part ithe p-centers, SIAM Journal on Applied Mathematics, 37, 3, 513-538, (1979) · Zbl 0432.90074
[8] Hooker, J.; Garfinkel, R.; Chen, C., Finite dominating sets for network location problems, Operations Research, 39, 1, 100-118, (1991) · Zbl 0744.90049
[9] Megiddo, N.; Tamir, A.; Zemel, E.; Chandrasekaran, R., An \(O(n \log^2 n)\) algorithm for the k-th longest path in a tree with applications to location problems, SIAM Journal on Computing, 10, 2, 328-337, (1981) · Zbl 0456.68071
[10] Tansel, B.; Francis, R.; Lowe, T.; Chen, M., Duality and distance constraints for the nonlinear p-center problem and covering problem on a tree network, Operations Research, 30, 4, 725-744, (1982) · Zbl 0486.90037
[11] Megiddo, N.; Tamir, A., New results on the complexity of p-centre problems, SIAM Journal on Computing, 12, 4, 751-758, (1983) · Zbl 0521.68037
[12] Jaeger, M.; Kariv, O., Algorithms for finding p-centers on a weighted tree (for relatively small p), Networks, 15, 3, 381-389, (1985) · Zbl 0579.90024
[13] Shaw, D. X., A unified limited column generation approach for facility location problems on trees, Annals of Operations Research, 87, 363-382, (1999) · Zbl 0924.90103
[14] Tansel, B. C.; Francis, R. L.; Lowe, T. J., State of the art—location on networksa survey. part I: the p-center and p-Median problems, Management Science, 29, 4, 482-497, (1983) · Zbl 0513.90022
[15] Tansel, B. C.; Francis, R. L.; Lowe, T. J., State of the art—location on networksa survey. part II: exploiting tree network structure, Management Science, 29, 4, 498-511, (1983) · Zbl 0513.90023
[16] Handler, G. Y.; Mirchandani, P. B., Location on networkstheory and algorithms, vol. 979, (1979), MIT Press Cambridge, MA
[17] Daskin, M. S., Network and discrete locationmodels, algorithms, and applications, (1995), Wiley New York
[18] Tansel, B. C., Discrete center problems, (Eiselt, H. A.; Marianov, V., Foundations of location analysis, (2011), Springer New York), 79-106, [Chapter 5] · Zbl 1387.90122
[19] Cornuéjols, G.; Nemhauser, G. L.; Wolsey, L. A., A canonical representation of simple plant location problems and its applications, SIAM Journal on Algebraic Discrete Methods, 1, 3, 261-272, (1980) · Zbl 0501.90032
[20] Christofides, N.; Viola, P., The optimum location of multi-centres on a graph, Operational Research Quarterly, 145-154, (1971) · Zbl 0219.05069
[21] Toregas, C.; Swain, R.; ReVelle, C.; Bergman, L., The location of emergency service facilities, Operations Research, 19, 6, 1363-1373, (1971) · Zbl 0224.90048
[22] Garfinkel, R.; Neebe, A.; Rao, M., The m-center problemminimax facility location, Management Science, 23, 10, 1133-1142, (1977) · Zbl 0369.90125
[23] Daskin, M. S., A new approach to solving the vertex p-center problem to optimalityalgorithm and computational results, Communications of the Operations Research Society of Japan, 45, 9, 428-436, (2000)
[24] Ilhan T, Pinar M. An efficient exact algorithm for the vertex p-center problem. 2001. URL 〈http://www.ie.bilkent.edu.tr/ mustafap/pubs/〉.
[25] khedhairi, Al-A.; Salhi, S., Enhancements to two exact algorithms for solving the vertex p-center problem, Journal of Mathematical Modelling and Algorithms, 4, 2, 129-147, (2005) · Zbl 1093.90004
[26] IBM. IBM ILOG CPLEX Optimization Studio. 2013 URL 〈www.ibm.com/software/products/us/en/ibmilogcpleoptistud/〉.
[27] González, T. F., Clustering to minimize the maximum intercluster distance, Theoretical Computer Science, 38, 293-306, (1985) · Zbl 0567.62048
[28] Floyd, R. W., Algorithm 97shortest path, Communications of ACM, 5, 6, 345-346, (1962)
[29] XINOX Software. JCreator—Java IDE. 2012. URL 〈http://www.jcreator.com/〉.
[30] Calik H. New formulations and exact solution methods for the capacitated and uncapacitated p-center location problem. PhD dissertation. Ankara, Turkey: Department of Industrial Engineering, Bilkent University; to appear.
[31] Francis, R. L.; Leon, F.; McGinnis, J.; White, J. A., Facility layout and locationan analytical approach, (1992), Prentice Hall Upper Saddle River, NJ
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.