IDEAS home Printed from https://ideas.repec.org/a/spr/comgts/v15y2018i3d10.1007_s10287-018-0321-1.html
   My bibliography  Save this article

New solution approaches for the maximum-reliability stochastic network interdiction problem

Author

Listed:
  • Eli Towle

    (University of Wisconsin–Madison)

  • James Luedtke

    (University of Wisconsin–Madison)

Abstract

We investigate methods to solve the maximum-reliability stochastic network interdiction problem (SNIP). In this problem, a defender interdicts arcs on a directed graph to minimize an attacker’s probability of undetected traversal through the network. The attacker’s origin and destination are unknown to the defender and assumed to be random. SNIP can be formulated as a stochastic mixed-integer program via a deterministic equivalent formulation (DEF). As the size of this DEF makes it impractical for solving large instances, current approaches to solving SNIP rely on modifications of Benders decomposition. We present two new approaches to solve SNIP. First, we introduce a new DEF that is significantly more compact than the standard DEF. Second, we propose a new path-based formulation of SNIP. The number of constraints required to define this formulation grows exponentially with the size of the network, but the model can be solved via delayed constraint generation. We present valid inequalities for this path-based formulation which are dependent on the structure of the interdicted arc probabilities. We propose a branch-and-cut (BC) algorithm to solve this new SNIP formulation. Computational results demonstrate that directly solving the more compact SNIP formulation and this BC algorithm both provide an improvement over a state-of-the-art implementation of Benders decomposition for this problem.

Suggested Citation

  • 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.
  • Handle: RePEc:spr:comgts:v:15:y:2018:i:3:d:10.1007_s10287-018-0321-1
    DOI: 10.1007/s10287-018-0321-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10287-018-0321-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10287-018-0321-1?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. Fisher, M.L. & Nemhauser, G.L. & Wolsey, L.A., 1978. "An analysis of approximations for maximizing submodular set functions - 1," LIDAM Reprints CORE 334, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. Richard Wollmer, 1964. "Removing Arcs from a Network," Operations Research, INFORMS, vol. 12(6), pages 934-940, December.
    4. Bruce Golden, 1978. "A problem in network interdiction," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 25(4), pages 711-713, December.
    5. Faiz A. Al-Khayyal & James E. Falk, 1983. "Jointly Constrained Biconvex Programming," Mathematics of Operations Research, INFORMS, vol. 8(2), pages 273-286, May.
    6. Miles Lubin & Iain Dunning, 2015. "Computing in Operations Research Using Julia," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 238-248, May.
    7. Gerald Brown & Matthew Carlyle & Javier Salmerón & Kevin Wood, 2006. "Defending Critical Infrastructure," Interfaces, INFORMS, vol. 36(6), pages 530-544, December.
    8. Nedialko Dimitrov & Dennis Michalopoulos & David Morton & Michael Nehme & Feng Pan & Elmira Popova & Erich Schneider & Gregory Thoreson, 2011. "Network deployment of radiation detectors with physics-based detection probability calculations," Annals of Operations Research, Springer, vol. 187(1), pages 207-228, July.
    9. Fisher, M.L. & Nemhauser, G.L. & Wolsey, L.A., 1978. "An analysis of approximations for maximizing submodular set functions," LIDAM Reprints CORE 341, 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. 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.
    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.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Laan, Corine M. & van der Mijden, Tom & Barros, Ana Isabel & Boucherie, Richard J. & Monsuur, Herman, 2017. "An interdiction game on a queueing network with multiple intruders," European Journal of Operational Research, Elsevier, vol. 260(3), pages 1069-1080.
    9. 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.
    10. Bloch, Francis & Chatterjee, Kalyan & Dutta, Bhaskar, 2023. "Attack and interception in networks," Theoretical Economics, Econometric Society, vol. 18(4), November.
    11. Young‐Soo Myung & Hyun‐Joon Kim, 2007. "Network disconnection problems in a centralized network," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(7), pages 710-719, October.
    12. Brian Lunday & Hanif Sherali, 2012. "Network interdiction to minimize the maximum probability of evasion with synergy between applied resources," Annals of Operations Research, Springer, vol. 196(1), pages 411-442, July.
    13. 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.
    14. 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.
    15. Ali Koç & David P. Morton, 2015. "Prioritization via Stochastic Optimization," Management Science, INFORMS, vol. 61(3), pages 586-603, March.
    16. Yan, Xihong & Ren, Xiaorong & Nie, Xiaofeng, 2022. "A budget allocation model for domestic airport network protection," Socio-Economic Planning Sciences, Elsevier, vol. 82(PB).
    17. Paola Cappanera & Maria Paola Scaparra, 2011. "Optimal Allocation of Protective Resources in Shortest-Path Networks," Transportation Science, INFORMS, vol. 45(1), pages 64-80, February.
    18. Annunziata Esposito Amideo & Stefano Starita & Maria Paola Scaparra, 2019. "Assessing Protection Strategies for Urban Rail Transit Systems: A Case-Study on the Central London Underground," Sustainability, MDPI, vol. 11(22), pages 1-21, November.
    19. Akgün, Ibrahim & Tansel, Barbaros Ç. & Kevin Wood, R., 2011. "The multi-terminal maximum-flow network-interdiction problem," European Journal of Operational Research, Elsevier, vol. 211(2), pages 241-251, June.
    20. Parajuli, Anubhuti & Kuzgunkaya, Onur & Vidyarthi, Navneet, 2017. "Responsive contingency planning of capacitated supply networks under disruption risks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 102(C), pages 13-37.

    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:spr:comgts:v:15:y:2018:i:3:d:10.1007_s10287-018-0321-1. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.