IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v308y2023i1p84-96.html
   My bibliography  Save this article

An efficient benders decomposition for the p-median problem

Author

Listed:
  • Duran-Mateluna, Cristian
  • Ales, Zacharie
  • Elloumi, Sourour

Abstract

The p-median problem is a classic discrete location problem with numerous applications. It aims to open p sites while minimizing the sum of the distances of each client to its nearest open site. We study a Benders decomposition of the most efficient formulation in the literature. We show that the Benders cuts can be separated in linear time. The Benders reformulation leads to a compact formulation for the p-median problem. We implement a two-phase Benders decomposition algorithm that outperforms state-of-the-art methods on benchmark instances by an order of magnitude and allows to exactly solve for the first time several instances among which are large TSP instances and BIRCH instances. We also show that our implementation easily applies to the uncapacitated facility location problem.

Suggested Citation

  • Duran-Mateluna, Cristian & Ales, Zacharie & Elloumi, Sourour, 2023. "An efficient benders decomposition for the p-median problem," European Journal of Operational Research, Elsevier, vol. 308(1), pages 84-96.
    • Handle: RePEc:eee:ejores:v:308:y:2023:i:1:p:84-96
    DOI: 10.1016/j.ejor.2022.11.033
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221722008864
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2022.11.033?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Irawan, Chandra Ade & Salhi, Said & Scaparra, Maria Paola, 2014. "An adaptive multiphase approach for large unconditional and conditional p-median problems," European Journal of Operational Research, Elsevier, vol. 237(2), pages 590-605.
    2. Olivier Briant & Denis Naddef, 2004. "The Optimal Diversity Management Problem," Operations Research, INFORMS, vol. 52(4), pages 515-526, August.
    3. Gaar, Elisabeth & Sinnl, Markus, 2022. "A scaleable projection‐based branch‐and‐cut algorithm for the p‐center problem," European Journal of Operational Research, Elsevier, vol. 303(1), pages 78-98.
    4. CORNUEJOLS, Gérard & NEMHAUSER, George L. & WOLSEY, Laurence A., 1980. "A canonical representation of simple plant location problems and its applications," LIDAM Reprints CORE 414, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Sourour Elloumi, 2010. "A tighter formulation of the p-median problem," Journal of Combinatorial Optimization, Springer, vol. 19(1), pages 69-83, January.
    6. Chandra Irawan & Said Salhi, 2015. "Solving large $$p$$ p -median problems by a multistage hybrid approach using demand points aggregation and variable neighbourhood search," Journal of Global Optimization, Springer, vol. 63(3), pages 537-554, November.
    7. Mladenovic, Nenad & Brimberg, Jack & Hansen, Pierre & Moreno-Perez, Jose A., 2007. "The p-median problem: A survey of metaheuristic approaches," European Journal of Operational Research, Elsevier, vol. 179(3), pages 927-939, June.
    8. Gerhard Reinelt, 1991. "TSPLIB—A Traveling Salesman Problem Library," INFORMS Journal on Computing, INFORMS, vol. 3(4), pages 376-384, November.
    9. Wangshu Mu & Daoqin Tong, 2020. "On solving large p-median problems," Environment and Planning B, , vol. 47(6), pages 981-996, July.
    10. Cordeau, Jean-François & Furini, Fabio & Ljubić, Ivana, 2019. "Benders decomposition for very large scale partial set covering and maximal covering location problems," European Journal of Operational Research, Elsevier, vol. 275(3), pages 882-896.
    11. T. L. Magnanti & R. T. Wong, 1981. "Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria," Operations Research, INFORMS, vol. 29(3), pages 464-484, June.
    12. Matteo Fischetti & Ivana Ljubić & Markus Sinnl, 2017. "Redesigning Benders Decomposition for Large-Scale Facility Location," Management Science, INFORMS, vol. 63(7), pages 2146-2162, July.
    13. An, Yu & Zeng, Bo & Zhang, Yu & Zhao, Long, 2014. "Reliable p-median facility location problem: two-stage robust models and algorithms," Transportation Research Part B: Methodological, Elsevier, vol. 64(C), pages 54-72.
    14. S. L. Hakimi, 1964. "Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph," Operations Research, INFORMS, vol. 12(3), pages 450-459, June.
    15. T. D. Klastorin, 1985. "The p-Median Problem for Cluster Analysis: A Comparative Test Using the Mixture Model Approach," Management Science, INFORMS, vol. 31(1), pages 84-95, January.
    16. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Sergio García & Martine Labbé & Alfredo Marín, 2011. "Solving Large p -Median Problems with a Radius Formulation," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 546-556, November.
    2. Camilo Ortiz-Astorquiza & Ivan Contreras & Gilbert Laporte, 2019. "An Exact Algorithm for Multilevel Uncapacitated Facility Location," Transportation Science, INFORMS, vol. 53(4), pages 1085-1106, July.
    3. Gaar, Elisabeth & Sinnl, Markus, 2022. "A scaleable projection‐based branch‐and‐cut algorithm for the p‐center problem," European Journal of Operational Research, Elsevier, vol. 303(1), pages 78-98.
    4. Lin, Yun Hui & Tian, Qingyun, 2021. "Branch-and-cut approach based on generalized benders decomposition for facility location with limited choice rule," European Journal of Operational Research, Elsevier, vol. 293(1), pages 109-119.
    5. S Salhi & A Al-Khedhairi, 2010. "Integrating heuristic information into exact methods: The case of the vertex p-centre problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(11), pages 1619-1631, November.
    6. Maher, Stephen J., 2021. "Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework," European Journal of Operational Research, Elsevier, vol. 290(2), pages 479-498.
    7. Michael Brusco & Douglas Steinley, 2015. "Affinity Propagation and Uncapacitated Facility Location Problems," Journal of Classification, Springer;The Classification Society, vol. 32(3), pages 443-480, October.
    8. Daniel Baena & Jordi Castro & Antonio Frangioni, 2020. "Stabilized Benders Methods for Large-Scale Combinatorial Optimization, with Application to Data Privacy," Management Science, INFORMS, vol. 66(7), pages 3051-3068, July.
    9. Lin, Yun Hui & Wang, Yuan & Lee, Loo Hay & Chew, Ek Peng, 2022. "Omnichannel facility location and fulfillment optimization," Transportation Research Part B: Methodological, Elsevier, vol. 163(C), pages 187-209.
    10. Snežana Tadić & Mladen Krstić & Željko Stević & Miloš Veljović, 2023. "Locating Collection and Delivery Points Using the p -Median Location Problem," Logistics, MDPI, vol. 7(1), pages 1-17, February.
    11. Benati, Stefano & García, Sergio, 2012. "A p-median problem with distance selection," DES - Working Papers. Statistics and Econometrics. WS ws121913, Universidad Carlos III de Madrid. Departamento de Estadística.
    12. Weninger, Dieter & Wolsey, Laurence A., 2023. "Benders-type branch-and-cut algorithms for capacitated facility location with single-sourcing," European Journal of Operational Research, Elsevier, vol. 310(1), pages 84-99.
    13. Aldrighetti, Riccardo & Battini, Daria & Ivanov, Dmitry & Zennaro, Ilenia, 2021. "Costs of resilience and disruptions in supply chain network design models: A review and future research directions," International Journal of Production Economics, Elsevier, vol. 235(C).
    14. Marilène Cherkesly & Claudio Contardo, 2021. "The conditional p-dispersion problem," Journal of Global Optimization, Springer, vol. 81(1), pages 23-83, September.
    15. Jesus Garcia-Diaz & Jairo Sanchez-Hernandez & Ricardo Menchaca-Mendez & Rolando Menchaca-Mendez, 2017. "When a worse approximation factor gives better performance: a 3-approximation algorithm for the vertex k-center problem," Journal of Heuristics, Springer, vol. 23(5), pages 349-366, October.
    16. Camilo Ortiz-Astorquiza & Jean-François Cordeau & Emma Frejinger, 2021. "The Locomotive Assignment Problem with Distributed Power at the Canadian National Railway Company," Transportation Science, INFORMS, vol. 55(2), pages 510-531, March.
    17. Teodor Gabriel Crainic & Mike Hewitt & Francesca Maggioni & Walter Rei, 2021. "Partial Benders Decomposition: General Methodology and Application to Stochastic Network Design," Transportation Science, INFORMS, vol. 55(2), pages 414-435, March.
    18. Neamatian Monemi, Rahimeh & Gelareh, Shahin & Nagih, Anass & Maculan, Nelson & Danach, Kassem, 2021. "Multi-period hub location problem with serial demands: A case study of humanitarian aids distribution in Lebanon," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    19. Nieto-Isaza, Santiago & Fontaine, Pirmin & Minner, Stefan, 2022. "The value of stochastic crowd resources and strategic location of mini-depots for last-mile delivery: A Benders decomposition approach," Transportation Research Part B: Methodological, Elsevier, vol. 157(C), pages 62-79.
    20. Alcaraz, Javier & Landete, Mercedes & Monge, Juan F., 2012. "Design and analysis of hybrid metaheuristics for the Reliability p-Median Problem," European Journal of Operational Research, Elsevier, vol. 222(1), pages 54-64.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:308:y:2023:i:1:p:84-96. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.