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

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%.