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

Weak flow cover inequalities for the capacitated facility location problem

Author

Listed:
  • Avella, P.
  • Boccia, M.
  • Mattia, S.
  • Rossi, F.

Abstract

The Capacitated Facility Location Problem calls for opening a set of facilities with capacity constraints, with the aim of satisfying at the minimum cost the demands of a set of customers. We present a new class of valid inequalities, the Weak Flow Cover inequalities. We show that Weak Flow Cover inequalities can be separated in polynomial time and turned into violated Flow Cover inequalities. In this way, we are able to provide a polynomial separation heuristic for the latter. Embedding the separation procedure into a cut-and-branch approach, we get results significantly better than those reported in the recent literature both for the lower and the upper bounds.

Suggested Citation

  • Avella, P. & Boccia, M. & Mattia, S. & Rossi, F., 2021. "Weak flow cover inequalities for the capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 289(2), pages 485-494.
    • Handle: RePEc:eee:ejores:v:289:y:2021:i:2:p:485-494
    DOI: 10.1016/j.ejor.2020.07.033
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720306445
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.07.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. Klose, Andreas & Gortz, Simon, 2007. "A branch-and-price algorithm for the capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1109-1125, June.
    2. Pasquale Avella & Maurizio Boccia, 2009. "A cutting plane algorithm for the capacitated facility location problem," Computational Optimization and Applications, Springer, vol. 43(1), pages 39-65, May.
    3. Klose, Andreas & Drexl, Andreas, 2005. "Facility location models for distribution system design," European Journal of Operational Research, Elsevier, vol. 162(1), pages 4-29, April.
    4. Andreas Klose & Andreas Drexl, 2005. "Lower Bounds for the Capacitated Facility Location Problem Based on Column Generation," Management Science, INFORMS, vol. 51(11), pages 1689-1705, November.
    5. LOUVEAUX, Quentin & WOLSEY, Laurence A., 2003. "Lifting, superadditivity, mixed integer rounding and single node flow sets revisited," LIDAM Reprints CORE 1659, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. Aardal, K. & Pochet, Y. & Wolsey, L. A., 1995. "Capacitated facility location: valid inequalities and facets," LIDAM Reprints CORE 1295, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. Elena Fernández & Mercedes Landete, 2015. "Fixed-Charge Facility Location Problems," Springer Books, in: Gilbert Laporte & Stefan Nickel & Francisco Saldanha da Gama (ed.), Location Science, edition 127, chapter 0, pages 47-77, Springer.
    8. Simon Görtz & Andreas Klose, 2012. "A Simple but Usually Fast Branch-and-Bound Algorithm for the Capacitated Facility Location Problem," INFORMS Journal on Computing, INFORMS, vol. 24(4), pages 597-610, November.
    9. LOUVEAUX, Quentin & WOLSEY, Laurence, 2003. "Lifting, superadditivity, mixed integer rounding and single node flow sets revisited," LIDAM Discussion Papers CORE 2003001, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    10. Cornuejols, G. & Sridharan, R. & Thizy, J. M., 1991. "A comparison of heuristics and relaxations for the capacitated plant location problem," European Journal of Operational Research, Elsevier, vol. 50(3), pages 280-297, February.
    11. Karen Aardal, 1998. "Reformulation of capacitated facility location problems:How redundant information can help," Annals of Operations Research, Springer, vol. 82(0), pages 289-308, August.
    12. Karen Aardal & Yves Pochet & Laurence A. Wolsey, 1995. "Capacitated Facility Location: Valid Inequalities and Facets," Mathematics of Operations Research, INFORMS, vol. 20(3), pages 562-582, August.
    13. D. Chinhyung Cho & Ellis L. Johnson & Manfred Padberg & M. R. Rao, 1983. "On the Uncapacitated Plant Location Problem. I: Valid Inequalities and Facets," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 579-589, November.
    14. Fischetti, Matteo & Ljubić, Ivana & Sinnl, Markus, 2016. "Benders decomposition without separability: A computational study for capacitated facility location problems," European Journal of Operational Research, Elsevier, vol. 253(3), pages 557-569.
    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. Christensen, Tue Rauff Lind & Klose, Andreas, 2021. "A fast exact method for the capacitated facility location problem with differentiable convex production costs," European Journal of Operational Research, Elsevier, vol. 292(3), pages 855-868.
    2. Fischetti, Matteo & Ljubić, Ivana & Sinnl, Markus, 2016. "Benders decomposition without separability: A computational study for capacitated facility location problems," European Journal of Operational Research, Elsevier, vol. 253(3), pages 557-569.
    3. Corberán, Ángel & Landete, Mercedes & Peiró, Juanjo & Saldanha-da-Gama, Francisco, 2020. "The facility location problem with capacity transfers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 138(C).
    4. Klose, Andreas & Gortz, Simon, 2007. "A branch-and-price algorithm for the capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1109-1125, June.
    5. Simon Görtz & Andreas Klose, 2012. "A Simple but Usually Fast Branch-and-Bound Algorithm for the Capacitated Facility Location Problem," INFORMS Journal on Computing, INFORMS, vol. 24(4), pages 597-610, November.
    6. M T Ramos & J Sáez, 2005. "Solving capacitated facility location problems by Fenchel cutting planes," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(3), pages 297-306, March.
    7. Han, Jialin & Zhang, Jiaxiang & Zeng, Bing & Mao, Mingsong, 2021. "Optimizing dynamic facility location-allocation for agricultural machinery maintenance using Benders decomposition," Omega, Elsevier, vol. 105(C).
    8. Drexl, Andreas & Klose, Andreas, 2001. "Facility location models for distribution system design," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 546, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    9. 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.
    10. Liu, Weiwei & Kong, Nan & Wang, Mingzheng & Zhang, Lingling, 2021. "Sustainable multi-commodity capacitated facility location problem with complementarity demand functions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    11. Pasquale Avella & Maurizio Boccia, 2009. "A cutting plane algorithm for the capacitated facility location problem," Computational Optimization and Applications, Springer, vol. 43(1), pages 39-65, May.
    12. Ortiz-Astorquiza, Camilo & Contreras, Ivan & Laporte, Gilbert, 2018. "Multi-level facility location problems," European Journal of Operational Research, Elsevier, vol. 267(3), pages 791-805.
    13. Klaus Büdenbender & Tore Grünert & Hans-Jürgen Sebastian, 2000. "A Hybrid Tabu Search/Branch-and-Bound Algorithm for the Direct Flight Network Design Problem," Transportation Science, INFORMS, vol. 34(4), pages 364-380, November.
    14. Filippi, C. & Guastaroba, G. & Speranza, M.G., 2021. "On single-source capacitated facility location with cost and fairness objectives," European Journal of Operational Research, Elsevier, vol. 289(3), pages 959-974.
    15. Yang, Zhen & Chen, Haoxun & Chu, Feng & Wang, Nengmin, 2019. "An effective hybrid approach to the two-stage capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 275(2), pages 467-480.
    16. Pelegrín, Mercedes, 2023. "New variants of the simple plant location problem and applications," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1094-1108.
    17. Klose, Andreas & Drexl, Andreas, 2001. "Combinatorial optimisation problems of the assignment type and a partitioning approach," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 545, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    18. Klose, Andreas, 2000. "A Lagrangean relax-and-cut approach for the two-stage capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 126(2), pages 408-421, October.
    19. Mervat Chouman & Teodor Gabriel Crainic & Bernard Gendron, 2017. "Commodity Representations and Cut-Set-Based Inequalities for Multicommodity Capacitated Fixed-Charge Network Design," Transportation Science, INFORMS, vol. 51(2), pages 650-667, May.
    20. Andreas Klose & Andreas Drexl, 2005. "Lower Bounds for the Capacitated Facility Location Problem Based on Column Generation," Management Science, INFORMS, vol. 51(11), pages 1689-1705, November.

    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:289:y:2021:i:2:p:485-494. 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.