查看文章

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 …