IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v29y2017i3p474-488.html
   My bibliography  Save this article

A Branch Decomposition Algorithm for the p -Median Problem

Author

Listed:
  • Caleb C. Fast

    (Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005)

  • Illya V. Hicks

    (Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005)

Abstract

In this paper, we use a branch decomposition technique to improve approximations to the p -median problem. Starting from a support graph produced either by a combination of heuristics or by linear programming, we use dynamic programming guided by a branch decomposition of that support graph to find the best p -median solution on the support graph. Our results show that when heuristics are used to build the support graph and the support graph has branchwidth at most 7, our algorithm is able to provide a solution of lower cost than any of the heuristic solutions. When linear programming is used to build the support graph and the support graph has branchwidth at most 7, then our algorithm provides better solutions than popular heuristics and is faster than integer programming. Thus, our algorithm is a useful practical tool when support graphs have branchwidth at most 7.

Suggested Citation

  • Caleb C. Fast & Illya V. Hicks, 2017. "A Branch Decomposition Algorithm for the p -Median Problem," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 474-488, August.
    • Handle: RePEc:inm:orijoc:v:29:y:2017:i:3:p:474-488
    DOI: 10.1287/ijoc.2016.0743
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2016.0743
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2016.0743?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
    ---><---

    References listed on IDEAS

    as
    1. Rolland, Erik & Schilling, David A. & Current, John R., 1997. "An efficient tabu search procedure for the p-Median Problem," European Journal of Operational Research, Elsevier, vol. 96(2), pages 329-342, January.
    2. Sourour Elloumi, 2010. "A tighter formulation of the p-median problem," Journal of Combinatorial Optimization, Springer, vol. 19(1), pages 69-83, January.
    3. William Cook & Paul Seymour, 2003. "Tour Merging via Branch-Decomposition," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 233-248, August.
    4. Beasley, J. E., 1985. "A note on solving large p-median problems," European Journal of Operational Research, Elsevier, vol. 21(2), pages 270-273, August.
    5. Gerhard Reinelt, 1991. "TSPLIB—A Traveling Salesman Problem Library," INFORMS Journal on Computing, INFORMS, vol. 3(4), pages 376-384, November.
    6. Hribar, Michelle & Daskin, Mark S., 1997. "A dynamic programming heuristic for the P-median problem," European Journal of Operational Research, Elsevier, vol. 101(3), pages 499-508, September.
    7. Amber Kunkel & Elizabeth Itallie & Duo Wu, 2014. "Optimal distribution of medical backpacks and health surveillance assistants in Malawi," Health Care Management Science, Springer, vol. 17(3), pages 230-244, September.
    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. Miriam Kießling & Sascha Kurz & Jörg Rambau, 2021. "An exact column-generation approach for the lot-type design problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(3), pages 741-780, October.

    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. 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.
    2. Mauricio Resende & Renato Werneck, 2007. "A fast swap-based local search procedure for location problems," Annals of Operations Research, Springer, vol. 150(1), pages 205-230, March.
    3. Daniel Martins & Gabriel M. Vianna & Isabel Rosseti & Simone L. Martins & Alexandre Plastino, 2018. "Making a state-of-the-art heuristic faster with data mining," Annals of Operations Research, Springer, vol. 263(1), pages 141-162, April.
    4. 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.
    5. Illya V. Hicks, 2005. "Planar Branch Decompositions II: The Cycle Method," INFORMS Journal on Computing, INFORMS, vol. 17(4), pages 413-421, November.
    6. 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.
    7. Illya V. Hicks, 2005. "Planar Branch Decompositions I: The Ratcatcher," INFORMS Journal on Computing, INFORMS, vol. 17(4), pages 402-412, November.
    8. William Cook & Sanjeeb Dash & Ricardo Fukasawa & Marcos Goycoolea, 2009. "Numerically Safe Gomory Mixed-Integer Cuts," INFORMS Journal on Computing, INFORMS, vol. 21(4), pages 641-649, November.
    9. Thiago Serra & Ryan J. O’Neil, 2020. "MIPLIBing: Seamless Benchmarking of Mathematical Optimization Problems and Metadata Extensions," SN Operations Research Forum, Springer, vol. 1(3), pages 1-6, September.
    10. Marilène Cherkesly & Claudio Contardo, 2021. "The conditional p-dispersion problem," Journal of Global Optimization, Springer, vol. 81(1), pages 23-83, September.
    11. Malaguti, Enrico & Martello, Silvano & Santini, Alberto, 2018. "The traveling salesman problem with pickups, deliveries, and draft limits," Omega, Elsevier, vol. 74(C), pages 50-58.
    12. Bernardino, Raquel & Paias, Ana, 2018. "Solving the family traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 267(2), pages 453-466.
    13. Ernst Althaus & Felix Rauterberg & Sarah Ziegler, 2020. "Computing Euclidean Steiner trees over segments," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 309-325, October.
    14. 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.
    15. 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).
    16. 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.
    17. 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.
    18. 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.
    19. 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.
    20. 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.

    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:inm:orijoc:v:29:y:2017:i:3:p:474-488. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.