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

Integer linear programming formulations for the maximum flow blocker problem

Author

Listed:
  • Bentoumi, Isma
  • Furini, Fabio
  • Mahjoub, A. Ridha
  • Martin, Sébastien

Abstract

Given a network with capacities and blocker costs associated with its arcs, we study the maximum flow blocker problem (FB). This problem seeks to identify a minimum-cost subset of arcs to be removed from the network, ensuring that the maximum flow value from the source to the destination in the remaining network does not exceed a specified threshold. The FB finds applications in telecommunication networks and monitoring of civil infrastructures, among other domains. We undertake a comprehensive study of several new integer linear programming (ILP) formulations designed for the FB. The first type of model, featuring an exponential number of constraints, is solved through tailored Branch-and-Cut algorithms. In contrast, the second type of ILP model, with a polynomial number of variables and constraints, is solved using a state-of-the-art ILP solver. The latter formulation establishes a structural connection between the FB and the maximum flow interdiction problem (FI), introducing a novel approach to obtaining solutions for each problem from the other. The ILP formulations proposed for solving the FB are evaluated thanks to a theoretical analysis assessing the strength of their LP relaxations. Additionally, the exact methods presented in this paper undergo a thorough comparison through an extensive computational campaign involving a set of real-world and synthetic instances. Our tests aim to evaluate the performance of the exact algorithms and identify the features of instances that can be solved with proven optimality.

Suggested Citation

  • Bentoumi, Isma & Furini, Fabio & Mahjoub, A. Ridha & Martin, Sébastien, 2025. "Integer linear programming formulations for the maximum flow blocker problem," European Journal of Operational Research, Elsevier, vol. 324(3), pages 742-758.
    • Handle: RePEc:eee:ejores:v:324:y:2025:i:3:p:742-758
    DOI: 10.1016/j.ejor.2025.02.013
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722172500116X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2025.02.013?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

    for a different version of it.

    References listed on IDEAS

    as
    1. Kelly J. Cormican & David P. Morton & R. Kevin Wood, 1998. "Stochastic Network Interdiction," Operations Research, INFORMS, vol. 46(2), pages 184-197, April.
    2. Smith, J. Cole & Song, Yongjia, 2020. "A survey of network interdiction models and algorithms," European Journal of Operational Research, Elsevier, vol. 283(3), pages 797-811.
    3. Furini, Fabio & Ljubić, Ivana & Martin, Sébastien & San Segundo, Pablo, 2019. "The maximum clique interdiction problem," European Journal of Operational Research, Elsevier, vol. 277(1), pages 112-127.
    4. Matteo Fischetti & Ivana Ljubić & Michele Monaci & Markus Sinnl, 2017. "A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs," Operations Research, INFORMS, vol. 65(6), pages 1615-1637, December.
    5. Wei, Ningji & Walteros, Jose L., 2022. "Integer programming methods for solving binary interdiction games," European Journal of Operational Research, Elsevier, vol. 302(2), pages 456-469.
    6. Gilberto Fernandes & Joel J. P. C. Rodrigues & Luiz Fernando Carvalho & Jalal F. Al-Muhtadi & Mario Lemes Proença, 2019. "A comprehensive survey on network anomaly detection," Telecommunication Systems: Modelling, Analysis, Design and Management, Springer, vol. 70(3), pages 447-489, March.
    7. Johannes O. Royset & R. Kevin Wood, 2007. "Solving the Bi-Objective Maximum-Flow Network-Interdiction Problem," INFORMS Journal on Computing, INFORMS, vol. 19(2), pages 175-184, May.
    8. Richard Wollmer, 1964. "Removing Arcs from a Network," Operations Research, INFORMS, vol. 12(6), pages 934-940, December.
    9. Türkoğulları, Yavuz B. & Taşkın, Z. Caner & Aras, Necati & Altınel, İ. Kuban, 2016. "Optimal berth allocation, time-variant quay crane assignment and scheduling with crane setups in container terminals," European Journal of Operational Research, Elsevier, vol. 254(3), pages 985-1001.
    10. Furini, Fabio & Ljubić, Ivana & San Segundo, Pablo & Zhao, Yanlu, 2021. "A branch-and-cut algorithm for the Edge Interdiction Clique Problem," European Journal of Operational Research, Elsevier, vol. 294(1), pages 54-69.
    11. Alan W. McMasters & Thomas M. Mustin, 1970. "Optimal interdiction of a supply network," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 17(3), pages 261-268, September.
    12. Stephan Dempe, 2020. "Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography," Springer Optimization and Its Applications, in: Stephan Dempe & Alain Zemkoho (ed.), Bilevel Optimization, chapter 0, pages 581-672, Springer.
    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. Claudio Contardo & Jorge A. Sefair, 2022. "A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 890-908, March.
    2. Kübra Tanınmış & Markus Sinnl, 2022. "A Branch-and-Cut Algorithm for Submodular Interdiction Games," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2634-2657, September.
    3. Leitner, Markus & Ljubić, Ivana & Monaci, Michele & Sinnl, Markus & Tanınmış, Kübra, 2023. "An exact method for binary fortification games," European Journal of Operational Research, Elsevier, vol. 307(3), pages 1026-1039.
    4. Cerulli, Martina & Serra, Domenico & Sorgente, Carmine & Archetti, Claudia & Ljubić, Ivana, 2023. "Mathematical programming formulations for the Collapsed k-Core Problem," European Journal of Operational Research, Elsevier, vol. 311(1), pages 56-72.
    5. Beck, Yasmine & Ljubić, Ivana & Schmidt, Martin, 2023. "A survey on bilevel optimization under uncertainty," European Journal of Operational Research, Elsevier, vol. 311(2), pages 401-426.
    6. Alice Paul & Susan E. Martonosi, 2024. "The all-pairs vitality-maximization (VIMAX) problem," Annals of Operations Research, Springer, vol. 338(2), pages 1019-1048, July.
    7. Chaya Losada & M. Scaparra & Richard Church & Mark Daskin, 2012. "The stochastic interdiction median problem with disruption intensity levels," Annals of Operations Research, Springer, vol. 201(1), pages 345-365, December.
    8. Vishal Bansal & Sachin Jayaswal & Ankur Sinha, 2024. "Capacitated multiple allocation hub location problems under the risk of interdiction: model formulations and solution approaches," Annals of Operations Research, Springer, vol. 332(1), pages 213-251, January.
    9. Bloch, Francis & Chatterjee, Kalyan & Dutta, Bhaskar, 2023. "Attack and interception in networks," Theoretical Economics, Econometric Society, vol. 18(4), November.
    10. Wei, Ningji & Walteros, Jose L., 2022. "Integer programming methods for solving binary interdiction games," European Journal of Operational Research, Elsevier, vol. 302(2), pages 456-469.
    11. Tayyebi, Javad & Mitra, Ankan & Sefair, Jorge A., 2023. "The continuous maximum capacity path interdiction problem," European Journal of Operational Research, Elsevier, vol. 305(1), pages 38-52.
    12. Yan, Xihong & Ren, Xiaorong & Nie, Xiaofeng, 2022. "A budget allocation model for domestic airport network protection," Socio-Economic Planning Sciences, Elsevier, vol. 82(PB).
    13. Jabarzare, Ziba & Zolfagharinia, Hossein & Najafi, Mehdi, 2020. "Dynamic interdiction networks with applications in illicit supply chains," Omega, Elsevier, vol. 96(C).
    14. Juan S. Borrero & Leonardo Lozano, 2021. "Modeling Defender-Attacker Problems as Robust Linear Programs with Mixed-Integer Uncertainty Sets," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1570-1589, October.
    15. Smith, J. Cole & Song, Yongjia, 2020. "A survey of network interdiction models and algorithms," European Journal of Operational Research, Elsevier, vol. 283(3), pages 797-811.
    16. Zhang, Jing & Zhuang, Jun & Behlendorf, Brandon, 2018. "Stochastic shortest path network interdiction with a case study of Arizona–Mexico border," Reliability Engineering and System Safety, Elsevier, vol. 179(C), pages 62-73.
    17. Starita, Stefano & Scaparra, Maria Paola, 2016. "Optimizing dynamic investment decisions for railway systems protection," European Journal of Operational Research, Elsevier, vol. 248(2), pages 543-557.
    18. Gedik, Ridvan & Medal, Hugh & Rainwater, Chase & Pohl, Ed A. & Mason, Scott J., 2014. "Vulnerability assessment and re-routing of freight trains under disruptions: A coal supply chain network application," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 71(C), pages 45-57.
    19. Shen, Yeming & Sharkey, Thomas C. & Szymanski, Boleslaw K. & Wallace, William (Al), 2021. "Interdicting interdependent contraband smuggling, money and money laundering networks," Socio-Economic Planning Sciences, Elsevier, vol. 78(C).
    20. Leonardo Lozano & J. Cole Smith, 2017. "A Backward Sampling Framework for Interdiction Problems with Fortification," INFORMS Journal on Computing, INFORMS, vol. 29(1), pages 123-139, February.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:324:y:2025:i:3:p:742-758. 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.