{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T20:38:29Z","timestamp":1784320709982,"version":"3.55.0"},"reference-count":26,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T00:00:00Z","timestamp":1724716800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Dicyt 062313AS,ANID\/FONDECYT Iniciaci\u00f3n","award":["11230129"],"award-info":[{"award-number":["11230129"]}]},{"name":"Dicyt 062313AS,ANID\/FONDECYT Iniciaci\u00f3n","award":["LPR21-02"],"award-info":[{"award-number":["LPR21-02"]}]},{"name":"Competition for Research Regular Projects","award":["11230129"],"award-info":[{"award-number":["11230129"]}]},{"name":"Competition for Research Regular Projects","award":["LPR21-02"],"award-info":[{"award-number":["LPR21-02"]}]},{"name":"Universidad Tecnol\u00f3gica Metropolitana","award":["11230129"],"award-info":[{"award-number":["11230129"]}]},{"name":"Universidad Tecnol\u00f3gica Metropolitana","award":["LPR21-02"],"award-info":[{"award-number":["LPR21-02"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>In this paper, the quadratic p-median optimization problem is discussed, where the goal is to connect users to a selected group of facilities (emergency services, telecommunications servers, healthcare facilities) at the lowest possible cost. The problem is aimed at minimizing the cost of connecting these selected facilities. The costs are symmetric, meaning connecting two different points is the same in both directions. This problem extends the traditional p-median problem, a combinatorial problem used in various fields like facility location, network design, transportation, supply chain networks, emergency services, healthcare, and education planning. Surprisingly, the quadratic version has not been thoroughly considered in the literature. The paper highlights the formulation of two mixed-integer quadratic programming models to find optimal solutions to this problem. One model is a classic formulation, and the other is based on set cover theory. Linear versions and Bender\u2019s decomposition formulations for each model are also derived. A Bender\u2019s decomposition is solved using an algorithm that adds constraints during each iteration to improve the solution. Lazy constraints in the Gurobi solver\u2019s branch and cut algorithm are dynamically added whenever a mixed-integer programming solution is found. Additionally, an efficient local search meta-heuristic is proposed that usually finds optimal solutions for tested instances. Challenging instances with up to 60 facilities and 2000 users are successfully solved. Our results show that Bender\u2019s models with lazy constraints are the most effective for Euclidean and random test cases, achieving optimal solutions in less CPU time. The meta-heuristic also finds near-optimal solutions rapidly for these cases.<\/jats:p>","DOI":"10.3390\/sym16091114","type":"journal-article","created":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T11:58:46Z","timestamp":1724759926000},"page":"1114","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Quadratic p-Median Problem: A Bender\u2019s Decomposition and a Meta-Heuristic Local-Based Approach"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2500-3294","authenticated-orcid":false,"given":"Pablo","family":"Adasme","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering, Universidad de Santiago de Chile, Avenida Ecuador 3519, Santiago 9170022, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4917-6798","authenticated-orcid":false,"given":"Andr\u00e9s","family":"Viveros","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, Universidad de Santiago de Chile, Avenida Ecuador 3519, Santiago 9170022, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6391-6863","authenticated-orcid":false,"given":"Ali","family":"Dehghan Firoozabadi","sequence":"additional","affiliation":[{"name":"Department of Electricity, Universidad Tecnol\u00f3gica Metropolitana, Av. Jose Pedro Alessandri 1242, Santiago 7800002, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2024,8,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/j.asoc.2018.03.008","article-title":"p-Median based formulations with backbone facility locations","volume":"67","author":"Adasme","year":"2018","journal-title":"Appl. Soft Comput."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1287\/opre.12.3.450","article-title":"Optimum location of switching centers and the absolute centers and medians of a graph","volume":"12","author":"Hakimi","year":"1964","journal-title":"Oper. Res."},{"key":"ref_3","first-page":"1","article-title":"Integrated Modeling for Location Analysis","volume":"9","author":"Mak","year":"2016","journal-title":"Found. Trends Technol. Inf. Oper. Manag."},{"key":"ref_4","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, MIT Press and McGraw-Hill."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Church, R.L., and Murray, A.T. (2009). Business Site Selection, Location Analysis, and GIS, John Wiley & Sons.","DOI":"10.1002\/9780470432761"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"102465","DOI":"10.1016\/j.tre.2021.102465","article-title":"Emergency facility location problems in logistics: Status and perspectives","volume":"154","author":"Wang","year":"2021","journal-title":"Transp. Res. Part Logist. Transp. Rev."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Drezner, Z., and Hamacher, H.W. (2002). Facility Location: Applications and Theory, Springer Science & Business Media.","DOI":"10.1007\/978-3-642-56082-8"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Hoadley, E.D., Jorgensen, B., Masters, C., Tuma, N., and Wulff, S. (2010). Strategic Facilities Planning: A Focus On Health Care. J. Serv. Sci. (JSS), 3.","DOI":"10.19030\/jss.v3i1.797"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Paji\u0107, V., Andreji\u0107, M., Jolovi\u0107, M., and Kilibarda, M. (2024). Strategic Warehouse Location Selection in Business Logistics: A Novel Approach Using IMF SWARA\u2013MARCOS\u2014A Case Study of a Serbian Logistics Service Provider. Mathematics, 12.","DOI":"10.3390\/math12050776"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.ejor.2014.11.030","article-title":"Models, solutions and enabling technologies in humanitarian logistics","volume":"244","author":"Ertem","year":"2015","journal-title":"Eur. J. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Hammad, A.W., Akbarnezhad, A., Haddad, A., and Vazquez, E.G. (2019). Sustainable Zoning, Land-Use Allocation and Facility Location Optimisation in Smart Cities. Energies, 12.","DOI":"10.3390\/en12071318"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1287\/ijoc.1100.0418","article-title":"Solving Large p-Median Problems with a Radius Formulation","volume":"23","year":"2011","journal-title":"INFORMS J. Comput."},{"key":"ref_13","unstructured":"Achterberg, T. (2024, June 25). Gurobi Solver. Available online: https:\/\/www.gurobi.com\/."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Bentahar, J., Awan, I., Younas, M., and Gr\u00f8nli, T.M. (2021). Quadratic p-Median Formulations with Connectivity Costs between Facilities. Mobile Web and Intelligent Information Systems, Springer. MobiWIS 2021. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-030-83164-6"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"801","DOI":"10.1016\/j.ejor.2016.12.005","article-title":"The Benders decomposition algorithm: A literature review","volume":"259","author":"Rahmaniani","year":"2017","journal-title":"Eur. J. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/S0377-2217(87)80007-3","article-title":"A quadratic integer program for the location of interacting hub facilities","volume":"32","year":"1987","journal-title":"Eur. J. Oper. Res."},{"key":"ref_17","unstructured":"Haicheng, L. (2010, January 24\u201326). Research on Distribution of Sink Nodes in Wireless Sensor Network. Proceedings of the 2010 Third International Symposium on Information Science and Engineering, Shanghai, China."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"981","DOI":"10.1177\/2399808319892598","article-title":"On solving large p-median problems","volume":"47","author":"Wangshu","year":"2020","journal-title":"Environ. Plan. Urban Anal. City Sci."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"100081","DOI":"10.1016\/j.ejco.2023.100081","article-title":"Revisiting a Cornu\u00e9jols-Nemhauser-Wolsey formulation for the p-median problem","volume":"12","author":"Agra","year":"2024","journal-title":"Euro J. Comput. Optim."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1016\/j.ejor.2024.02.032","article-title":"The Hamiltonian p-median problem: Polyhedral results and branch-and-cut algorithms","volume":"316","author":"Barbato","year":"2024","journal-title":"Eur. J. Oper. Res."},{"key":"ref_21","unstructured":"Farahani, R.Z., and Hekmatfar, M. (2009). Facility Location: Concepts, Models, Algorithms and Case Studies, Springer Science & Business Media."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Laporte, G., Nickel, S., and Saldanha da Gama, F. (2015). The p-Median Problem. Location Science, Springer.","DOI":"10.1007\/978-3-319-13111-5"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Laporte, G., Nickel, S., and Saldanha da Gama, F. (2019). p-Median Problems. Location Science, Springer.","DOI":"10.1007\/978-3-030-32177-2"},{"key":"ref_24","first-page":"17","article-title":"Applications de l\u00e1lgebre de boole en recherche operationelle","volume":"4","author":"Fortet","year":"1960","journal-title":"Rev. Fr. Rech. Oper."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Bachem, A., and Kern, W. (1992). Linear Programming Duality: An Introduction to Oriented Matroids (Universitext), Springer. [1992nd ed.].","DOI":"10.1007\/978-3-642-58152-6"},{"key":"ref_26","unstructured":"George, L.N., and Laurence, A.W. (1988). Integer and Combinatorial Optimization, Wiley."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/16\/9\/1114\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T15:43:45Z","timestamp":1760111025000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/16\/9\/1114"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,27]]},"references-count":26,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2024,9]]}},"alternative-id":["sym16091114"],"URL":"https:\/\/doi.org\/10.3390\/sym16091114","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,27]]}}}