Robust maximum flow network interdiction considering uncertainties in arc capacity and resource consumption

Darshan Chauhan (), Avinash Unnikrishnan (), Stephen D. Boyles () and Priyadarshan N. Patil ()
Additional contact information
Darshan Chauhan: Portland State University
Avinash Unnikrishnan: The University of Alabama at Birmingham
Stephen D. Boyles: The University of Texas at Austin
Priyadarshan N. Patil: Independent Researcher

Annals of Operations Research, 2024, vol. 335, issue 2, No 4, 689-725

Abstract: Abstract This article discusses a robust network interdiction problem considering uncertainties in arc capacities and resource consumption. The problem involves two players: an adversary seeking to maximize the flow of a commodity through the network and an interdictor whose objective is to minimize this flow. The interdictor plays first and selects network arcs to interdict, subject to a resource constraint. The problem is formulated as a bilevel problem, and an upper bound single level mix-integer linear formulation is derived. The upper bound formulation is solved using three heuristics tailored for this problem and the network structure, based on Lagrangian relaxation and Benders’ decomposition. On average, each heuristic provides a reduction in run time of at least 85% compared to a state-of-the-art solver. Enhanced Benders’ decomposition achieves a solution with an optimality gap of less than 5% for all tested instances. Sensitivity analyses are conducted for the level of uncertainty in network parameters and the uncertainty budget. Robust decisions are also compared to decisions not accounting for uncertainty to evaluate the value of robustness, showing a reduction in simulation maximum flows by as much as 89.5%.

Keywords: Network interdiction; Robust optimization; Maximum flow; Uncertainty; Lagrangian Relaxation; Benders’ Decomposition (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-023-05812-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:335:y:2024:i:2:d:10.1007_s10479-023-05812-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-023-05812-6

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().