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

A survey of network interdiction models and algorithms

Author

Listed:
  • Smith, J. Cole
  • Song, Yongjia

Abstract

This paper discusses the development of interdiction optimization models and algorithms, with an emphasis on mathematical programming techniques and future research challenges in the field. After presenting basic interdiction concepts and notation, we recount the motivation and models behind founding research in the network interdiction field. Next, we examine some of the most common means of solving interdiction problems, focusing on dualization models and extended formulations solvable by row-generation techniques. We then examine contemporary interdiction problems involving incomplete information, information asymmetry, stochasticity, and dynamic play. We conclude by discussing several emerging applications in the field of network interdiction.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:283:y:2020:i:3:p:797-811
    DOI: 10.1016/j.ejor.2019.06.024
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719305156
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2019.06.024?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. Kelly J. Cormican & David P. Morton & R. Kevin Wood, 1998. "Stochastic Network Interdiction," Operations Research, INFORMS, vol. 46(2), pages 184-197, April.
    2. Nail Orkun Baycik & Thomas C. Sharkey & Chase E. Rainwater, 2018. "Interdicting layered physical and information flow networks," IISE Transactions, Taylor & Francis Journals, vol. 50(4), pages 316-331, April.
    3. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    4. Ravindra K. Ahuja & James B. Orlin, 2001. "Inverse Optimization," Operations Research, INFORMS, vol. 49(5), pages 771-783, October.
    5. Yuan, Wei & Zhao, Long & Zeng, Bo, 2014. "Optimal power grid protection through a defender–attacker–defender model," Reliability Engineering and System Safety, Elsevier, vol. 121(C), pages 83-89.
    6. J. Cole Smith & Churlzu Lim & Aydın Alptekinoğlu, 2009. "New product introduction against a predator: A bilevel mixed‐integer programming approach," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(8), pages 714-729, December.
    7. Gerald G. Brown & W. Matthew Carlyle & Robert C. Harney & Eric M. Skroch & R. Kevin Wood, 2009. "Interdicting a Nuclear-Weapons Project," Operations Research, INFORMS, vol. 57(4), pages 866-877, August.
    8. P. M. Ghare & D. C. Montgomery & W. C. Turner, 1971. "Optimal interdiction policy for a flow network," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 18(1), pages 37-45, March.
    9. Noam Goldberg, 2017. "Non‐zero‐sum nonlinear network path interdiction with an application to inspection in terror networks," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(2), pages 139-153, March.
    10. 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.
    11. H. Donald Ratliff & G. Thomas Sicilia & S. H. Lubore, 1975. "Finding the n Most Vital Links in Flow Networks," Management Science, INFORMS, vol. 21(5), pages 531-539, January.
    12. Rocco S., Claudio M. & Emmanuel Ramirez-Marquez, José & Salazar A., Daniel E., 2010. "Bi and tri-objective optimization in the deterministic network interdiction problem," Reliability Engineering and System Safety, Elsevier, vol. 95(8), pages 887-896.
    13. S. Rasoul Etesami & Tamer Başar, 2019. "Dynamic Games in Cyber-Physical Security: An Overview," Dynamic Games and Applications, Springer, vol. 9(4), pages 884-913, December.
    14. Richard Wollmer, 1964. "Removing Arcs from a Network," Operations Research, INFORMS, vol. 12(6), pages 934-940, December.
    15. Jorge A. Sefair & J. Cole Smith, 2017. "Exact algorithms and bounds for the dynamic assignment interdiction problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(5), pages 373-387, August.
    16. Jun Zhuang & Vicki M. Bier, 2007. "Balancing Terrorism and Natural Disasters---Defensive Strategy with Endogenous Attacker Effort," Operations Research, INFORMS, vol. 55(5), pages 976-991, October.
    17. Laura McLay & Jamie Lloyd & Emily Niman, 2011. "Interdicting nuclear material on cargo containers using knapsack problem models," Annals of Operations Research, Springer, vol. 187(1), pages 185-205, July.
    18. Eli Towle & James Luedtke, 2018. "New solution approaches for the maximum-reliability stochastic network interdiction problem," Computational Management Science, Springer, vol. 15(3), pages 455-477, October.
    19. Bruce Golden, 1978. "A problem in network interdiction," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 25(4), pages 711-713, December.
    20. David P. Morton & R. Kevin Wood, 1999. "Restricted-Recourse Bounds for Stochastic Linear Programming," Operations Research, INFORMS, vol. 47(6), pages 943-956, December.
    21. Gianni Codato & Matteo Fischetti, 2006. "Combinatorial Benders' Cuts for Mixed-Integer Linear Programming," Operations Research, INFORMS, vol. 54(4), pages 756-766, August.
    22. Alexander Mitsos, 2010. "Global solution of nonlinear mixed-integer bilevel programs," Journal of Global Optimization, Springer, vol. 47(4), pages 557-582, August.
    23. Baykal-Gürsoy, Melike & Duan, Zhe & Poor, H. Vincent & Garnaev, Andrey, 2014. "Infrastructure security games," European Journal of Operational Research, Elsevier, vol. 239(2), pages 469-478.
    24. Alan Washburn & Kevin Wood, 1995. "Two-Person Zero-Sum Games for Network Interdiction," Operations Research, INFORMS, vol. 43(2), pages 243-251, April.
    25. GÜNLÜK, Oktay & POCHET, Yves, 2001. "Mixing mixed-integer inequalities," LIDAM Reprints CORE 1504, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    26. Kelly M. Sullivan & David P. Morton & Feng Pan & J. Cole Smith, 2014. "Securing a border under asymmetric information," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(2), pages 91-100, March.
    27. 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.
    28. Ajay Malaviya & Chase Rainwater & Thomas Sharkey, 2012. "Multi-period network interdiction problems with applications to city-level drug enforcement," IISE Transactions, Taylor & Francis Journals, vol. 44(5), pages 368-380.
    29. 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.
    30. Yongjia Song & Siqian Shen, 2016. "Risk-Averse Shortest Path Interdiction," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 527-539, August.
    31. Peiqiu Guan & Meilin He & Jun Zhuang & Stephen C. Hora, 2017. "Modeling a Multitarget Attacker–Defender Game with Budget Constraints," Decision Analysis, INFORMS, vol. 14(2), pages 87-107, June.
    32. Leonardo Lozano & J. Cole Smith, 2017. "A Value-Function-Based Exact Approach for the Bilevel Mixed-Integer Programming Problem," Operations Research, INFORMS, vol. 65(3), pages 768-786, June.
    33. Alberto Caprara & Margarida Carvalho & Andrea Lodi & Gerhard J. Woeginger, 2016. "Bilevel Knapsack with Interdiction Constraints," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 319-333, May.
    34. Matteo Fischetti & Ivana Ljubić & Michele Monaci & Markus Sinnl, 2019. "Interdiction Games and Monotonicity, with Application to Knapsack Problems," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 390-410, April.
    35. Gerald Brown & Matthew Carlyle & Javier Salmerón & Kevin Wood, 2006. "Defending Critical Infrastructure," Interfaces, INFORMS, vol. 36(6), pages 530-544, December.
    36. Powell, Robert, 2007. "Defending against Terrorist Attacks with Limited Resources," American Political Science Review, Cambridge University Press, vol. 101(3), pages 527-541, August.
    37. Konrad, Renata A. & Trapp, Andrew C. & Palmbach, Timothy M. & Blom, Jeffrey S., 2017. "Overcoming human trafficking via operations research and analytics: Opportunities for methods, models, and applications," European Journal of Operational Research, Elsevier, vol. 259(2), pages 733-745.
    38. Lemaréchal, C. & Nemirovskii, A. & Nesterov, Y., 1995. "New variants of bundle methods," LIDAM Reprints CORE 1166, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    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. Jing Yang & Juan S. Borrero & Oleg A. Prokopyev & Denis Sauré, 2021. "Sequential Shortest Path Interdiction with Incomplete Information and Limited Feedback," Decision Analysis, INFORMS, vol. 18(3), pages 218-244, September.
    2. Kosmas, Daniel & Sharkey, Thomas C. & Mitchell, John E. & Maass, Kayse Lee & Martin, Lauren, 2023. "Interdicting restructuring networks with applications in illicit trafficking," European Journal of Operational Research, Elsevier, vol. 308(2), pages 832-851.
    3. Cheung, Kam-Fung & Bell, Michael G.H., 2021. "Improving connectivity of compromised digital networks via algebraic connectivity maximisation," European Journal of Operational Research, Elsevier, vol. 294(1), pages 353-364.
    4. Bloch, Francis & Chatterjee, Kalyan & Dutta, Bhaskar, 2023. "Attack and interception in networks," Theoretical Economics, Econometric Society, vol. 18(4), November.
    5. 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.
    6. Eric DuBois & Ashley Peper & Laura A. Albert, 2023. "Interdicting Attack Plans with Boundedly Rational Players and Multiple Attackers: An Adversarial Risk Analysis Approach," Decision Analysis, INFORMS, vol. 20(3), pages 202-219, September.
    7. 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.
    8. Oster, Matthew R. & King, Ethan & Bakker, Craig & Bhattacharya, Arnab & Chatterjee, Samrat & Pan, Feng, 2023. "Multi-level optimization with the koopman operator for data-driven, domain-aware, and dynamic system security," Reliability Engineering and System Safety, Elsevier, vol. 237(C).
    9. Nguyen, Kien Trung & Hung, Nguyen Thanh, 2021. "The minmax regret inverse maximum weight problem," Applied Mathematics and Computation, Elsevier, vol. 407(C).
    10. 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.
    11. 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.
    12. Carayannis, Elias G. & Grigoroudis, Evangelos & Wurth, Bernd, 2022. "OR for entrepreneurial ecosystems: A problem-oriented review and agenda," European Journal of Operational Research, Elsevier, vol. 300(3), pages 791-808.
    13. Nicolas Fröhlich & Stefan Ruzika, 2022. "Interdicting facilities in tree networks," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(1), pages 95-118, April.
    14. Parajuli, Anubhuti & Kuzgunkaya, Onur & Vidyarthi, Navneet, 2021. "The impact of congestion on protection decisions in supply networks under disruptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    15. 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).
    16. Keskin, Burcu B. & Griffin, Emily C. & Prell, Jonathan O. & Dilkina, Bistra & Ferber, Aaron & MacDonald, John & Hilend, Rowan & Griffis, Stanley & Gore, Meredith L., 2023. "Quantitative Investigation of Wildlife Trafficking Supply Chains: A Review," Omega, Elsevier, vol. 115(C).
    17. Utsav Sadana & Erick Delage, 2023. "The Value of Randomized Strategies in Distributionally Robust Risk-Averse Network Interdiction Problems," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 216-232, January.
    18. Yan, Xihong & Ren, Xiaorong & Nie, Xiaofeng, 2022. "A budget allocation model for domestic airport network protection," Socio-Economic Planning Sciences, Elsevier, vol. 82(PB).
    19. Tian, Meng & Dong, Zhengcheng & Gong, Li & Wang, Xianpei, 2024. "Line hardening strategies for resilient power systems considering cyber-topology interdependence," Reliability Engineering and System Safety, Elsevier, vol. 241(C).
    20. Xiaodan Xie & Felipe Aros‐Vera, 2022. "An interdependent network interdiction model for disrupting sex trafficking networks," Production and Operations Management, Production and Operations Management Society, vol. 31(6), pages 2695-2713, June.
    21. 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.
    22. Emma S. Johnson & Santanu Subhas Dey, 2022. "A Scalable Lower Bound for the Worst-Case Relay Attack Problem on the Transmission Grid," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2296-2312, July.
    23. 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.
    24. 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.
    25. Fränk Plein & Johannes Thürauf & Martine Labbé & Martin Schmidt, 2022. "A bilevel optimization approach to decide the feasibility of bookings in the European gas market," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 95(3), pages 409-449, June.

    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. 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.
    3. Yan, Xihong & Ren, Xiaorong & Nie, Xiaofeng, 2022. "A budget allocation model for domestic airport network protection," Socio-Economic Planning Sciences, Elsevier, vol. 82(PB).
    4. Abumoslem Mohammadi & Javad Tayyebi, 2019. "Maximum Capacity Path Interdiction Problem with Fixed Costs," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(04), pages 1-21, August.
    5. Keskin, Burcu B. & Griffin, Emily C. & Prell, Jonathan O. & Dilkina, Bistra & Ferber, Aaron & MacDonald, John & Hilend, Rowan & Griffis, Stanley & Gore, Meredith L., 2023. "Quantitative Investigation of Wildlife Trafficking Supply Chains: A Review," Omega, Elsevier, vol. 115(C).
    6. 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.
    7. Jabarzare, Ziba & Zolfagharinia, Hossein & Najafi, Mehdi, 2020. "Dynamic interdiction networks with applications in illicit supply chains," Omega, Elsevier, vol. 96(C).
    8. 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.
    9. Nguyen, Di H. & Smith, J. Cole, 2022. "Network interdiction with asymmetric cost uncertainty," European Journal of Operational Research, Elsevier, vol. 297(1), pages 239-251.
    10. Kosanoglu, Fuat & Bier, Vicki M., 2020. "Target-oriented utility for interdiction of transportation networks," Reliability Engineering and System Safety, Elsevier, vol. 197(C).
    11. 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.
    12. 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.
    13. Bloch, Francis & Chatterjee, Kalyan & Dutta, Bhaskar, 2023. "Attack and interception in networks," Theoretical Economics, Econometric Society, vol. 18(4), November.
    14. 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.
    15. 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.
    16. Matteo Fischetti & Ivana Ljubić & Michele Monaci & Markus Sinnl, 2019. "Interdiction Games and Monotonicity, with Application to Knapsack Problems," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 390-410, April.
    17. 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.
    18. Matthews, Logan R. & Gounaris, Chrysanthos E. & Kevrekidis, Ioannis G., 2019. "Designing networks with resiliency to edge failures using two-stage robust optimization," European Journal of Operational Research, Elsevier, vol. 279(3), pages 704-720.
    19. 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.
    20. Xiang, Yin, 2023. "Minimizing the maximal reliable path with a nodal interdiction model considering resource sharing," Reliability Engineering and System Safety, Elsevier, vol. 239(C).

    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:283:y:2020:i:3:p:797-811. 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.