IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v196y2012i1p411-44210.1007-s10479-012-1135-0.html
   My bibliography  Save this article

Network interdiction to minimize the maximum probability of evasion with synergy between applied resources

Author

Listed:
  • Brian Lunday
  • Hanif Sherali

Abstract

In this paper, we model and solve the network interdiction problem of minimizing the maximum probability of evasion by an entity traversing a network from a given source to a designated terminus, while incorporating novel forms of superadditive synergy between resources applied to arcs in the network. Inspired primarily by operations to coordinate Iraqi and U.S. security forces seeking to interdict an evader attempting to avoid detection while transiting part of the nearly rectilinear street network in East Baghdad, this study motivates and examines either linear or concave (nonlinear) synergy relationships between the applied resources within our formulations. We also propose an alternative model for sequential overt and covert deployment of subsets of interdiction resources, and conduct theoretical as well as empirical comparative analyses between models for purely overt (with or without synergy) and composite overt-covert strategies to provide insights into absolute and relative threshold criteria for recommended resource utilization. Our empirical results confirm the value of tactical patience regarding decisions on the covert utilization of resources for network interdiction. Furthermore, considering non-integral and integral resource allocations, we identify (theoretically and empirically) parametric characteristics of instances that exhibit the relative worth of employing partially covert operations. Under the relatively more practical scenario involving integral resource allocations, we demonstrate that the composite overt-covert strategy of deploying resources has a greater potential to improve over a purely overt resource deployment strategy, both with and without synergy, particularly when costs are positively correlated, resources are plentiful, and a sufficiently high ratio of covert to overt resources exists. Moreover, should an interdictor be able to ascertain an optimal evader path, the potential and magnitude of this relative improvement for the overt-covert resource allocation strategy is significantly greater. Copyright Springer Science+Business Media, LLC 2012

Suggested Citation

  • 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.
    • Handle: RePEc:spr:annopr:v:196:y:2012:i:1:p:411-442:10.1007/s10479-012-1135-0
    DOI: 10.1007/s10479-012-1135-0
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-012-1135-0
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-012-1135-0?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. 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.
    2. J. Cole Smith & Churlzu Lim, 2008. "Algorithms for Network Interdiction and Fortification Games," Springer Optimization and Its Applications, in: Altannar Chinchuluun & Panos M. Pardalos & Athanasios Migdalas & Leonidas Pitsoulis (ed.), Pareto Optimality, Game Theory And Equilibria, pages 609-644, Springer.
    3. Gerald Brown & Matthew Carlyle & Javier Salmerón & Kevin Wood, 2006. "Defending Critical Infrastructure," Interfaces, INFORMS, vol. 36(6), pages 530-544, December.
    4. Scott Shorey Brown, 1980. "Optimal Search for a Moving Target in Discrete Time and Space," Operations Research, INFORMS, vol. 28(6), pages 1275-1289, December.
    5. Kelly J. Cormican & David P. Morton & R. Kevin Wood, 1998. "Stochastic Network Interdiction," Operations Research, INFORMS, vol. 46(2), pages 184-197, April.
    6. Harald Held & Raymond Hemmecke & David L. Woodruff, 2005. "A decomposition algorithm applied to planning the interdiction of stochastic networks," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(4), pages 321-328, June.
    7. Kjell Hausken, 2011. "Strategic defense and attack of series systems when agents move sequentially," IISE Transactions, Taylor & Francis Journals, vol. 43(7), pages 483-504.
    8. Evert Meijers, 2005. "Polycentric Urban Regions and the Quest for Synergy: Is a Network of Cities More than the Sum of the Parts?," Urban Studies, Urban Studies Journal Limited, vol. 42(4), pages 765-781, April.
    9. Alan Washburn & Kevin Wood, 1995. "Two-Person Zero-Sum Games for Network Interdiction," Operations Research, INFORMS, vol. 43(2), pages 243-251, April.
    10. Bruce Golden, 1978. "A problem in network interdiction," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 25(4), pages 711-713, December.
    11. Anna Nagurney & Trisha Woolley, 2010. "Environmental and Cost Synergy in Supply Chain Network Integration in Mergers and Acquisitions," Lecture Notes in Economics and Mathematical Systems, in: Matthias Ehrgott & Boris Naujoks & Theodor J. Stewart & Jyrki Wallenius (ed.), Multiple Criteria Decision Making for Sustainable Energy and Transportation Systems, pages 57-78, Springer.
    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. 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.
    3. Tim Holzmann & J. Cole Smith, 2019. "Shortest path interdiction problem with arc improvement recourse: A multiobjective approach," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(3), pages 230-252, April.
    4. 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.
    5. Hosseini, Seyedmohsen & Barker, Kash & Ramirez-Marquez, Jose E., 2016. "A review of definitions and measures of system resilience," Reliability Engineering and System Safety, Elsevier, vol. 145(C), pages 47-61.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    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. 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.
    11. Bloch, Francis & Chatterjee, Kalyan & Dutta, Bhaskar, 2023. "Attack and interception in networks," Theoretical Economics, Econometric Society, vol. 18(4), November.
    12. 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.
    13. Pengfei Zhang & Neng Fan, 2017. "Analysis of budget for interdiction on multicommodity network flows," Journal of Global Optimization, Springer, vol. 67(3), pages 495-525, March.
    14. Dimitris Bertsimas & Ebrahim Nasrabadi & Sebastian Stiller, 2013. "Robust and Adaptive Network Flows," Operations Research, INFORMS, vol. 61(5), pages 1218-1242, October.
    15. Yan, Xihong & Ren, Xiaorong & Nie, Xiaofeng, 2022. "A budget allocation model for domestic airport network protection," Socio-Economic Planning Sciences, Elsevier, vol. 82(PB).
    16. 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.
    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. 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. 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.
    20. 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.

    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:annopr:v:196:y:2012:i:1:p:411-442:10.1007/s10479-012-1135-0. 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.