×

zbMATH — the first resource for mathematics

A scalable exact algorithm for the vertex \(p\)-center problem. (English) Zbl 1458.90423
Summary: The vertex \(p\)-center problem consists in selecting \(p\) centers among a finite set of candidates and assigning a set of clients to them, with the aim of minimizing the maximum dissimilarity between a client and its associated center. State-of-the-art algorithms for the problem are based on the solution of a series of covering subproblems, and are particularly efficient when additional reduction rules are used to limit the size of the subproblems. In fact, these algorithms do not scale well when the cardinality of the dissimilarity matrix grows above a few million entries, as the time and space required to compute and store the matrix start dominating those required for solving the subproblems. We introduce a scalable relaxation-based iterative algorithm that does not rely on the computation of the entire matrix, but rather relies on the computation of a typically much smaller sub-matrix that is only enlarged if deemed necessary. This method can solve to proven optimality \(p\)-center problems derived from the TSP library and containing up to one million clients for small but realistic values of \(p\).
Reviewer: Reviewer (Berlin)

MSC:
90B80 Discrete location and assignment
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Al-khedhairi, A.; Salhi, S., Enhancements to two exact algorithms for solving the vertex p-center problem, J. Math. Modell. Algo., 4, 2, 129-147, (2005) · Zbl 1093.90004
[2] Albareda-Sambola, M.; Díaz, J.; Fernández, E., Lagrangean duals and exact solution to the capacitated p-center problem, Eur. J. Oper. Res., 201, 1, 71-81, (2010) · Zbl 1177.90241
[3] Aloise, D.; Contardo, C., A sampling-based exact algorithm for the solution of the minimax diameter clustering problem, J. Global Optim., 71, 3, 613-630, (2018) · Zbl 1402.90207
[4] Bai, C.; Kang, L.; Shan, E., The connected p-center problem on cactus graphs, Theor. Comput. Sci, (2017)
[5] Berman; Drezner, A new formulation for the conditional p-median and p-center problems, Oper. Res. Lett., 36, 4, 481-483, (2008) · Zbl 1155.90332
[6] Bezanson, J.; Edelman, A.; Karpinski, S.; Shah, V. B., Julia: a fresh approach to numerical computing, SIAM Rev., 59, 1, 65-98, (2017) · Zbl 1356.68030
[7] Calik, H.; Labbé, M.; Yaman, H., p-center problems, (Laporte, G.; Nickel, S.; Saldanha da Gama, F., Location Science, (2015), Springer), 79-92
[8] Calik, H.; Tansel, B. C., Double bound method for solving the p-center location problem, Comput. Oper. Res., 40, 12, 2991-2999, (2013) · Zbl 1348.90384
[9] Callaghan, B.; Salhi, S.; Brimberg, J., Optimal solutions for the continuous p-centre problem and related α-neighbour and conditional problems: a relaxation-based algorithm, J. Oper. Res. Soc, (2018)
[10] Callaghan, B.; Salhi, S.; Nagy, G., Speeding up the optimal method of Drezner for the p-centre problem in the plane, Eur. J. Oper. Res., 257, 3, 722-734, (2017) · Zbl 1394.90383
[11] Caruso, C.; Colorni, A.; Aloi, L., Dominant, an algorithm for the p-center problem, Eur. J. Oper. Res., 149, 1, 53-64, (2003) · Zbl 1035.90037
[12] Chaudhuri, S.; Garg, N.; Ravi, R., The p-neighbor k-center problem, Inf. Process. Lett., 65, 3, 131-134, (1998) · Zbl 1338.68290
[13] Chen, D.; Chen, R., New relaxation-based algorithms for the optimal solution of the continuous and discrete p-center problems, Comput. Oper. Res., 36, 5, 1646-1655, (2009) · Zbl 1177.90246
[14] Chen, D.; Chen, R., Optimal algorithms for the α-neighbor p-center problem, Eur. J. Oper. Res., 225, 1, 36-43, (2013) · Zbl 1292.90159
[15] Chen, D. Z.; Wang, H., Efficient algorithms for the weighted k-center problem on a real line, (Asano, T.; Nakano, S.-i.; Okamoto, Y.; Watanabe, O., Algorithms and Computation, (2011), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 584-593 · Zbl 1350.68259
[16] Chen, R.; Handler, G. Y., Relaxation method for the solution of the minimax location-allocation problem in euclidean space, Nav. Res. Logist., 34, 6, 775-788, (1987) · Zbl 0648.90026
[17] Chen, R.; Handler, G. Y., The conditional p-center problem in the plane, Nav. Res. Logist., 40, 1, 117-127, (1993) · Zbl 0769.90061
[18] Chu, S. C.; Chu, L., A modeling framework for hospital location and service allocation, Int. Trans. Oper. Res., 7, 6, 539-568, (2000)
[19] Current, J.; Daskin, M. S.; Schilling, D., Discrete network location models, (Drezner, Z.; Hamacher, H. W., Facility Location: Applications and Theory, (2002), Springer), 81-118 · Zbl 1061.90070
[20] Daskin, M., Center problems, (Daskin, M., Network and Discrete Location: Models, Algorithms, and Applications, (1995), Wiley, New York), 154-197
[21] (Daskin, M., Network and Discrete Location: Models, Algorithms, and Applications, (1995), Wiley, New York) · Zbl 0870.90076
[22] Daskin, M., A new approach to solving the vertex p-center problem to optimality: algorithm and computational results, Commun. Oper. Res. Soc. Jpn., 45, 9, 428-436, (2000)
[23] Drezner, Z., Conditional p-center problems, Transp. Sci., 23, 1, 51-53, (1989) · Zbl 0675.90025
[24] Dunning, I.; Huchette, J.; Lubin, M., Jump: a modeling language for mathematical optimization, SIAM Rev., 59, 2, 295-320, (2017) · Zbl 1368.90002
[25] Elloumi, S.; Labbé, M.; Pochet, Y., A new formulation and resolution method for the p-center problem, INFORMS J. Comput., 16, 1, 84-94, (2004) · Zbl 1239.90103
[26] Francis, R. L.; Lowe, T. J.; Rayco, M. B.; Tamir, A., Aggregation error for location models: survey and analysis, Ann. Oper. Res., 167, 1, 171-208, (2009) · Zbl 1173.90005
[27] Francis, R. L.; McGinnis, L. F.; White, J. A., Facility Layout and Location: an Analytical Approach, (1992), Pearson College Division
[28] Gower, J. C., A general coefficient of similarity and some of its properties, Biometrics, 27, 4, 857, (1971)
[29] Grangier, P.; Gendreau, M.; Lehuédé, F.; Rousseau, L.-M., An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization, Eur. J. Oper. Res., 254, 1, 80-91, (2016) · Zbl 1346.90116
[30] Gurobi Optimization, Inc., 2017. Gurobi optimizer reference manual.
[31] Hakimi, S. L., Optimum locations of switching centers and the absolute centers and medians of a graph, Oper. Res., 12, 3, 450-459, (1964) · Zbl 0123.00305
[32] Hansen, P.; Brimberg, J.; Urošević, D.; Mladenović, N., Solving large p-median clustering problems by primal-dual variable neighborhood search, Data Min. Knowl. Discov., 19, 3, 351-375, (2009)
[33] Ilhan, T.; Özsoy, F. A.; Pınar, M.Ç., An efficient exact algorithm for the vertex p-center problem and computational experiments for different set covering subproblems, Technical Report, (2002)
[34] Ilhan, T.; Pınar, M.Ç., An efficient exact algorithm for the vertex p-center problem, Technical Report, (2001)
[35] Irawan, C. A.; Salhi, S.; Drezner, Z., Hybrid meta-heuristics with VNS and exact methods: application to large unconditional and conditional vertex p-centre problems, J. Heurist., 22, 4, 507-537, (2015)
[36] Kariv, O.; Hakimi, S., An algorithmic approach to network location problems. I: the p-centers, SIAM J. Appl. Math., 37, 3, 513-538, (1979) · Zbl 0432.90074
[37] Khuller, S.; Sussmann, Y., The capacitated k-center problem, SIAM J. Discrete Math., 13, 3, 403-418, (2000) · Zbl 0947.05073
[38] Kramer, R.; Iori, M.; Vidal, T., Mathematical models and search algorithms for the capacitated p-center problem, Technical Report, (2018)
[39] Krumke, S., On a generalization of the p-center problem, Inf. Process. Lett., 56, 2, 67-71, (1995)
[40] Labbé, M.; Laporte, G., Maximizing user convenience and postal service efficiency in post box location, Belgian J. Oper. Res., Stat. Comput. Sci., 26, 21-35, (1986)
[41] Lourenço, H.; Martin, O.; Stützle, T., Iterated local search: framework and applications, (Gendreau, M.; Potvin, J.-Y., Handbook of Metaheuristics. Handbook of Metaheuristics, International Series in Operations Research and Management Science, (2010), Springer), 362-397
[42] Lu, C.-C., Robust weighted vertex p-center model considering uncertain data: an application to emergency management, Eur. J. Oper. Res., 230, 1, 113-121, (2013) · Zbl 1317.90166
[43] Martínez-Merino, L. I.; Albareda-Sambola, M.; Rodríguez-Chía, A. M., The probabilistic p-center problem: planning service for potential customers, Eur. J. Oper. Res., 262, 2, 509-520, (2017) · Zbl 1375.90167
[44] Masuyama, S.; Ibaraki, T.; Hasegawa, T., The computational complexity of the m-center problems on the plane, Trans. IECE Jpn., E64, 57-64, (1981)
[45] Minieka, E., The m-center problem, SIAM Rev., 12, 1, 138-139, (1970) · Zbl 0193.24204
[46] Özsoy, F.; Pınar, M., An exact algorithm for the capacitated vertex p-center problem, Comput. Oper. Res., 33, 5, 1420-1436, (2006) · Zbl 1126.90039
[47] Plane, D. R.; Hendrick, T. E., Mathematical programming and the location of fire companies for the Denver fire department, Oper. Res., 25, 4, 563-578, (1977) · Zbl 0371.90074
[48] Tansel, B.; Francis, R.; Lowe, T. J., State of the art-location on networks: a survey. Part I: the p-center and p-median problems, Manage. Sci., 29, 4, 482-497, (1983) · Zbl 0513.90022
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.