Abstract
The p-center problem consists in selecting p centers among M to cover N clients, such that the maximal distance between a client and its closest selected center is minimized. For this problem we propose two new and compact integer formulations.
Our first formulation is an improvement of a previous formulation. It significantly decreases the number of constraints while preserving the optimal value of the linear relaxation. Our second formulation contains less variables and constraints but it has a weaker linear relaxation bound.
We besides introduce an algorithm which enables us to compute strong bounds and significantly reduce the size of our formulations.
Finally, the efficiency of the algorithm and the proposed formulations are compared in terms of quality of the linear relaxation and computation time over instances from OR-Library.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Beasley, J.E.: OR-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41, 1069–1072 (1990)
Calik, H., Labbé, M., Yaman, H.: p-center problems. In: Laporte, G., Nickel, S., da Gama, F.S. (eds.) Location Science, pp. 79–92. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-13111-5_4
Calik, H., Tansel, B.C.: Double bound method for solving the p-center location problem. Comput. Oper. Res. 40(12), 2991–2999 (2013)
Daskin, M.S.: Network and Discrete Location Analysis. Wiley, New York (1995)
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)
Ferone, D., Festa, P., Napoletano, A., Resende, M.G.C.: A new local search for the p-center problem based on the critical vertex concept. In: Battiti, R., Kvasov, D.E., Sergeyev, Y.D. (eds.) LION 2017. LNCS, vol. 10556, pp. 79–92. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-69404-7_6
Ferone, D., Festa, P., Napoletano, A., Resende, M.G.C.: On the fast solution of the p-center problem. In: 2017 19th International Conference on Transparent Optical Networks (ICTON), pp. 1–4, July 2017
Sayah, D., Irnich, S.: A new compact formulation for the discrete p-dispersion problem. Eur. J. Oper. Res. 256(1), 62–67 (2017)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Ales, Z., Elloumi, S. (2018). Compact MILP Formulations for the p-Center Problem. In: Lee, J., Rinaldi, G., Mahjoub, A. (eds) Combinatorial Optimization. ISCO 2018. Lecture Notes in Computer Science(), vol 10856. Springer, Cham. https://doi.org/10.1007/978-3-319-96151-4_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-96151-4_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-96150-7
Online ISBN: 978-3-319-96151-4
eBook Packages: Computer ScienceComputer Science (R0)