Abstract
In this paper, we consider the problem of minimizing simultaneously the total connectivity cost of a set of users to a set of facility nodes and between facilities themselves. The problem arises as an extension of the p-Median problem, which is a classical combinatorial optimization problem. We propose two mixed-integer quadratic programming models which allow obtaining optimal solutions. Example application domains where the proposed models can be utilized include modeling and management of smart transportation and wireless networks, to name a few. Our first model is derived as an extension of the classical p-Median formulation. Whereas the second one is an alternative set-covering model. Finally, we linearize these models and strengthen them by imposing additional linearized quadratic cuts. We solve hard instances with up to 60 facility nodes and 350 users with the Gurobi solver. Our preliminary numerical results indicate that the linear set-covering formulation allows solving all tested instances to optimality in significantly less computational effort, which is not possible to achieve with the other proposed models.
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
Adasme, P.: p-Median based formulations with backbone facility locations. Appl. Soft Comput. 67, 261–275 (2018)
Adasme, P., Andrade, R., Lisser, A.: Minimum cost dominating tree sensor networks under probabilistic constraints. Comput. Netw. 112, 208–222 (2017)
García, S., Labbé, M., Marín, A.: Solving large p-median problems with a radius formulation. INFORMS J. Comput. 23(4), 546–556 (2011)
Achterberg, T.: Gurobi solver. https://www.gurobi.com/
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press and McGraw-Hill, Cumberland (2009)
Fortet, R.: Applications de lálgebre de boole en recherche operationelle. Rev. Fr. Rech. Oper. 4, 17–26 (1960)
Haicheng, L.: Research on distribution of sink nodes in wireless sensor network. In: 2010 Third International Symposium on Information Science and Engineering, pp. 122–124 (2010). https://doi.org/10.1109/ISISE.2010.56
Hakimi, S.L.: Optimum location of switching centers and the absolute centers and medians of a graph. Oper. Res. 12, 450–459 (1964)
Ho-Yin, M., Zuo-Jun, M.S.: Integrated Modeling for Location Analysis. In: Now Foundations and Trends, p. 164 (2016)
O’Kelly, M.E.: A quadratic integer program for the location of interacting hub facilities. Eur. J. Oper. Res. 32, 393–404 (1987)
Wangshu, M., Daoqin, T.: On solving large p-median problems. Environ. Planning B Urban Anal. City Sci. 47(6), 981–996 (2020)
Acknowledgments
The authors acknowledge the financial support from Projects: FONDECYT No. 11180107 and FONDECYT No. 3190147.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Sandoval, C., Adasme, P., Firoozabadi, A.D. (2021). Quadratic p-Median Formulations with Connectivity Costs Between Facilities. In: Bentahar, J., Awan, I., Younas, M., Grønli, TM. (eds) Mobile Web and Intelligent Information Systems. MobiWIS 2021. Lecture Notes in Computer Science(), vol 12814. Springer, Cham. https://doi.org/10.1007/978-3-030-83164-6_8
Download citation
DOI: https://doi.org/10.1007/978-3-030-83164-6_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-83163-9
Online ISBN: 978-3-030-83164-6
eBook Packages: Computer ScienceComputer Science (R0)