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

Integer programming methods for solving binary interdiction games

Author

Listed:
  • Wei, Ningji
  • Walteros, Jose L.

Abstract

This paper studies a general class of interdiction problems in which the solution space of both the leader and follower are characterized by two discrete sets denoted the leader’s strategy set and the follower’s structure set. In this setting, the interaction between any strategy-structure pair is assumed to be binary, in the sense that the strategy selected by the leader either interacts or not with the follower’s choice of structure and, if it does, then the structure becomes unavailable for the follower. There are many interdiction games defined by this setup, including problems where the leader wishes to attack some type of network structures, such as shortest paths, minimum spanning trees, and minimum dominating sets, among others. We study a general set-covering type of formulation that can be used for solving this class of problems and analyze several properties of the convex hull of its solutions. We develop a wide class of valid inequalities that generalizes and extends several others that have appeared in the literature in recent years. We provide conditions for them to be facet-defining and conclude with a general discussion about their separation. Several examples of problems in the context of network interdiction are presented to help with the exposition.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:302:y:2022:i:2:p:456-469
    DOI: 10.1016/j.ejor.2022.01.009
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221722000091
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2022.01.009?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. Mahdavi Pajouh, Foad & Walteros, Jose L. & Boginski, Vladimir & Pasiliao, Eduardo L., 2015. "Minimum edge blocker dominating set problem," European Journal of Operational Research, Elsevier, vol. 247(1), pages 16-26.
    2. Kelly J. Cormican & David P. Morton & R. Kevin Wood, 1998. "Stochastic Network Interdiction," Operations Research, INFORMS, vol. 46(2), pages 184-197, April.
    3. 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.
    4. 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.
    5. C. Audet & P. Hansen & B. Jaumard & G. Savard, 1997. "Links Between Linear Bilevel and Mixed 0–1 Programming Problems," Journal of Optimization Theory and Applications, Springer, vol. 93(2), pages 273-300, May.
    6. 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.
    7. Foad Mahdavi Pajouh, 2020. "Minimum cost edge blocker clique problem," Annals of Operations Research, Springer, vol. 294(1), pages 345-376, November.
    8. 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.
    9. 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.
    10. 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.
    11. M. Hosein Zare & Juan S. Borrero & Bo Zeng & Oleg A. Prokopyev, 2019. "A note on linearized reformulations for a class of bilevel linear integer problems," Annals of Operations Research, Springer, vol. 272(1), pages 99-117, January.
    12. M. Sánchez-García & M. Sobrón & B. Vitoriano, 1998. "On the set covering polytope:Facets with coefficients in {0, 1, 2, 3}," Annals of Operations Research, Springer, vol. 81(0), pages 343-356, June.
    13. Shenglong Zhou & Alain B. Zemkoho & Andrey Tin, 2020. "BOLIB: Bilevel Optimization LIBrary of Test Problems," Springer Optimization and Its Applications, in: Stephan Dempe & Alain Zemkoho (ed.), Bilevel Optimization, chapter 0, pages 563-580, Springer.
    14. 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.
    15. Cristina Bazgan & Sonia Toubaline & Daniel Vanderpooten, 2013. "Critical edges/nodes for the minimum spanning tree problem: complexity and approximation," Journal of Combinatorial Optimization, Springer, vol. 26(1), pages 178-189, July.
    16. 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.
    17. Ningji Wei & Jose L. Walteros & Foad Mahdavi Pajouh, 2021. "Integer Programming Formulations for Minimum Spanning Tree Interdiction," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1461-1480, October.
    18. Gerald Brown & Matthew Carlyle & Javier Salmerón & Kevin Wood, 2006. "Defending Critical Infrastructure," Interfaces, INFORMS, vol. 36(6), pages 530-544, December.
    19. Alexander Veremyev & Oleg A. Prokopyev & Eduardo L. Pasiliao, 2014. "An integer programming framework for critical elements detection in graphs," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 233-273, July.
    20. 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.
    21. Jorge A. Sefair & J. Cole Smith & Miguel A. Acevedo & Robert J. Fletcher, 2017. "A defender-attacker model and algorithm for maximizing weighted expected hitting time with application to conservation planning," IISE Transactions, Taylor & Francis Journals, vol. 49(12), pages 1112-1128, December.
    22. 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.
    23. Marco Di Summa & Andrea Grosso & Marco Locatelli, 2012. "Branch and cut algorithms for detecting critical nodes in undirected graphs," Computational Optimization and Applications, Springer, vol. 53(3), pages 649-680, December.
    24. 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.
    25. Atamturk, Alper & Nemhauser, George L. & Savelsbergh, Martin W. P., 2000. "Conflict graphs in solving integer programming problems," European Journal of Operational Research, Elsevier, vol. 121(1), pages 40-55, February.
    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. 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.

    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. 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.
    2. Ningji Wei & Jose L. Walteros & Foad Mahdavi Pajouh, 2021. "Integer Programming Formulations for Minimum Spanning Tree Interdiction," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1461-1480, October.
    3. 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.
    4. Zhong, Haonan & Mahdavi Pajouh, Foad & A． Prokopyev, Oleg, 2023. "On designing networks resilient to clique blockers," European Journal of Operational Research, Elsevier, vol. 307(1), pages 20-32.
    5. 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.
    6. Foad Mahdavi Pajouh, 2020. "Minimum cost edge blocker clique problem," Annals of Operations Research, Springer, vol. 294(1), pages 345-376, November.
    7. 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.
    8. 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.
    9. 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).
    10. Yan, Xihong & Ren, Xiaorong & Nie, Xiaofeng, 2022. "A budget allocation model for domestic airport network protection," Socio-Economic Planning Sciences, Elsevier, vol. 82(PB).
    11. 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.
    12. Juan S. Borrero & Oleg A. Prokopyev & Denis Sauré, 2019. "Sequential Interdiction with Incomplete Information and Learning," Operations Research, INFORMS, vol. 67(1), pages 72-89, January.
    13. Bloch, Francis & Chatterjee, Kalyan & Dutta, Bhaskar, 2023. "Attack and interception in networks," Theoretical Economics, Econometric Society, vol. 18(4), November.
    14. Karwowski, Jan & Mańdziuk, Jacek, 2019. "A Monte Carlo Tree Search approach to finding efficient patrolling schemes on graphs," European Journal of Operational Research, Elsevier, vol. 277(1), pages 255-268.
    15. 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.
    16. 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.
    17. Hooshmand, F. & Mirarabrazi, F. & MirHassani, S.A., 2020. "Efficient Benders decomposition for distance-based critical node detection problem," Omega, Elsevier, vol. 93(C).
    18. Ramamoorthy, Prasanna & Jayaswal, Sachin & Sinha, Ankur & Vidyarthi, Navneet, 2018. "Multiple allocation hub interdiction and protection problems: Model formulations and solution approaches," European Journal of Operational Research, Elsevier, vol. 270(1), pages 230-245.
    19. 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.
    20. 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.

    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:302:y:2022:i:2:p:456-469. 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.