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

Network interdiction with asymmetric cost uncertainty

Author

Listed:
  • Nguyen, Di H.
  • Smith, J. Cole

Abstract

We study a shortest-path interdiction problem in which the interdictor acts first to lengthen a subset of arcs, and an evader acts second to select a shortest path across the network. In this problem, the cost for an evader’s arc consists of a base cost if the arc is not interdicted, plus an additional cost that is incurred if the arc is interdicted. The interdictor is not aware of the base costs when the interdiction action is taken, but does know that the base cost values are uniformly distributed within given (arc-specific) intervals. The evader, on the other hand, observes the exact value of the base costs, plus the additional costs due to interdiction actions. The interdictor’s problem is thus to maximize the expected minimum cost attainable by the evader. We provide a partitioning algorithm for computing an exact optimal solution to this problem, leveraging bounds gleaned from Jensen’s inequality as proposed in an earlier study on a maximum-flow interdiction problem. We also provide several algorithmic strategies for accelerating the convergence of the algorithm and demonstrate their effectiveness on randomly generated instances.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:297:y:2022:i:1:p:239-251
    DOI: 10.1016/j.ejor.2021.04.055
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721003908
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.04.055?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. Mete, Huseyin Onur & Zabinsky, Zelda B., 2010. "Stochastic optimization of medical supply location and distribution in disaster management," International Journal of Production Economics, Elsevier, vol. 126(1), pages 76-84, July.
    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. 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.
    4. 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.
    5. 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.
    6. Juan S. Borrero & Oleg A. Prokopyev & Denis Sauré, 2016. "Sequential Shortest Path Interdiction with Incomplete Information," Decision Analysis, INFORMS, vol. 13(1), pages 68-98, March.
    7. Richard Wollmer, 1964. "Removing Arcs from a Network," Operations Research, INFORMS, vol. 12(6), pages 934-940, December.
    8. Gerald Brown & Matthew Carlyle & Javier Salmerón & Kevin Wood, 2006. "Defending Critical Infrastructure," Interfaces, INFORMS, vol. 36(6), pages 530-544, December.
    9. Bruce Golden, 1978. "A problem in network interdiction," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 25(4), pages 711-713, December.
    10. 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.
    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. 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).
    2. 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.

    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. 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. 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.
    4. 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.
    5. 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.
    6. Yan, Xihong & Ren, Xiaorong & Nie, Xiaofeng, 2022. "A budget allocation model for domestic airport network protection," Socio-Economic Planning Sciences, Elsevier, vol. 82(PB).
    7. 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.
    8. 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.
    9. 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.
    10. 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).
    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. 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.
    13. Bloch, Francis & Chatterjee, Kalyan & Dutta, Bhaskar, 2023. "Attack and interception in networks," Theoretical Economics, Econometric Society, vol. 18(4), November.
    14. 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.
    15. 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.
    16. 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.
    17. 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.
    18. Sushil Gupta & Martin K. Starr & Reza Zanjirani Farahani & Mahsa Mahboob Ghodsi, 2020. "Prevention of Terrorism–An Assessment of Prior POM Work and Future Potentials," Production and Operations Management, Production and Operations Management Society, vol. 29(7), pages 1789-1815, July.
    19. 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.
    20. 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.

    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:297:y:2022:i:1:p:239-251. 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.