Interdiction of a Mixed-Integer Linear System

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.



View Interdiction of a Mixed-Integer Linear System