A system-interdiction problem can be modeled as a bilevel program in which the upper level models interdiction decisions and the lower level models system operation. This paper studies MILSIP, a mixed-integer linear system interdiction problem, which assumes binary interdiction decisions and models system operations through a mixed-integer linear program. To solve large-scale instances of MILSIP, we apply Benders decomposition to a single-level reformulation of MILSIP. We identify ``significant'' linear programming subproblems whose feasibility implies the optimality of MILSIP. We propose an algorithm that that solves in each iteration: a relaxed master problem, a lower-level problem, and a significant subproblem. We demonstrate the algorithm's computational capabilities on a natural gas transmission system with 32 interdictable components. Numerical tests show that our algorithm solves certain problem instances an order of magnitude faster than an alternative algorithm from the literature.

## Article

Download

View Interdiction of a Mixed-Integer Linear System