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

A scaleable projection‐based branch‐and‐cut algorithm for the p‐center problem

Author

Listed:
  • Gaar, Elisabeth
  • Sinnl, Markus

Abstract

The p-center problem (pCP) is a fundamental problem in location science, where we are given customer demand points and possible facility locations, and we want to choose p of these locations to open a facility such that the maximum distance of any customer demand point to its closest open facility is minimized. State-of-the-art solution approaches of pCP use its connection to the set cover problem to solve pCP in an iterative fashion by repeatedly solving set cover problems. The classical textbook integer programming (IP) formulation of pCP is usually dismissed due to its size and bad linear programming (LP)-relaxation bounds.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:303:y:2022:i:1:p:78-98
    DOI: 10.1016/j.ejor.2022.02.016
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221722001187
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2022.02.016?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. Gerhard Reinelt, 1991. "TSPLIB—A Traveling Salesman Problem Library," INFORMS Journal on Computing, INFORMS, vol. 3(4), pages 376-384, November.
    2. 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.
    3. R. S. Garfinkel & A. W. Neebe & M. R. Rao, 1977. "The m-Center Problem: Minimax Facility Location," Management Science, INFORMS, vol. 23(10), pages 1133-1142, June.
    4. Sourour Elloumi & Martine Labbé & Yves Pochet, 2004. "A New Formulation and Resolution Method for the p-Center Problem," INFORMS Journal on Computing, INFORMS, vol. 16(1), pages 84-94, February.
    5. S. L. Hakimi, 1965. "Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems," Operations Research, INFORMS, vol. 13(3), pages 462-475, June.
    6. 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.
    7. Caruso, C. & Colorni, A. & Aloi, L., 2003. "Dominant, an algorithm for the p-center problem," European Journal of Operational Research, Elsevier, vol. 149(1), pages 53-64, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. 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.

    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. 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.
    2. Blanco, Víctor & Gázquez, Ricardo & Ponce, Diego & Puerto, Justo, 2023. "A branch-and-price approach for the continuous multifacility monotone ordered median problem," European Journal of Operational Research, Elsevier, vol. 306(1), pages 105-126.
    3. Ljubić, Ivana & Pozo, Miguel A. & Puerto, Justo & Torrejón, Alberto, 2024. "Benders decomposition for the discrete ordered median problem," European Journal of Operational Research, Elsevier, vol. 317(3), pages 858-874.
    4. 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.
    5. Chou, Xiaochen & Dell’Amico, Mauro & Jamal, Jafar & Montemanni, Roberto, 2023. "Precedence-Constrained arborescences," European Journal of Operational Research, Elsevier, vol. 307(2), pages 575-589.
    6. F. Antonio Medrano, 2020. "The complete vertex p-center problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 327-343, October.
    7. 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.
    8. Rafael Blanquero & Emilio Carrizosa & Amaya Nogales-Gómez & Frank Plastria, 2014. "Single-facility huff location problems on networks," Annals of Operations Research, Springer, vol. 222(1), pages 175-195, November.
    9. Martins, Francisco Leonardo Bezerra & do Nascimento, José Cláudio, 2022. "Power law dynamics in genealogical graphs," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 596(C).
    10. Marjan Marzban & Qian-Ping Gu & Xiaohua Jia, 2016. "New analysis and computational study for the planar connected dominating set problem," Journal of Combinatorial Optimization, Springer, vol. 32(1), pages 198-225, July.
    11. Ferrer, José M. & Martín-Campo, F. Javier & Ortuño, M. Teresa & Pedraza-Martínez, Alfonso J. & Tirado, Gregorio & Vitoriano, Begoña, 2018. "Multi-criteria optimization for last mile distribution of disaster relief aid: Test cases and applications," European Journal of Operational Research, Elsevier, vol. 269(2), pages 501-515.
    12. R. Baldacci & E. Hadjiconstantinou & A. Mingozzi, 2004. "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation," Operations Research, INFORMS, vol. 52(5), pages 723-738, October.
    13. Roberto Tadei & Guido Perboli & Francesca Perfetti, 2017. "The multi-path Traveling Salesman Problem with stochastic travel costs," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 3-23, March.
    14. 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.
    15. Lancia, Giuseppe & Vidoni, Paolo, 2020. "Finding the largest triangle in a graph in expected quadratic time," European Journal of Operational Research, Elsevier, vol. 286(2), pages 458-467.
    16. 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.
    17. Oya Ekin Karaşan & A. Ridha Mahjoub & Onur Özkök & Hande Yaman, 2014. "Survivability in Hierarchical Telecommunications Networks Under Dual Homing," INFORMS Journal on Computing, INFORMS, vol. 26(1), pages 1-15, February.
    18. Paredes-Belmar, Germán & Montero, Elizabeth & Lüer-Villagra, Armin & Marianov, Vladimir & Araya-Sassi, Claudio, 2022. "Vehicle routing for milk collection with gradual blending: A case arising in Chile," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1403-1416.
    19. Thanh Tan Doan & Nathalie Bostel & Minh Hoàng Hà & Vu Hoang Vuong Nguyen, 2023. "New mixed integer linear programming models and an iterated local search for the clustered traveling salesman problem with relaxed priority rule," Journal of Combinatorial Optimization, Springer, vol. 46(1), pages 1-27, August.
    20. Pop, Petrică C. & Cosma, Ovidiu & Sabo, Cosmin & Sitar, Corina Pop, 2024. "A comprehensive survey on the generalized traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 314(3), pages 819-835.

    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:303:y:2022:i:1:p:78-98. 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.