Worst-Case Interdiction Analysis of Large-Scale Electric Power Grids

This paper generalizes Benders decomposition to maximize a nonconcave objective function and uses that decomposition to solve an electric power grid interdiction problem. Under one empirically verified assumption, the solution to this bilevel optimization problem identifies a set of components, limited by cardinality or interdiction resource, whose destruction maximizes economic losses to customers (and can thereby guide defensive measures). The decomposition subproblem typically incorporates a set of do optimal power-flow models that cover various states of repair after an attack, along with a load-duration curve. Test problems describe a regional power grid in the United States with approximately 5000 buses, 6000 lines, and 500 generators. Solution time on a 2-GHz personal computer is approximately one hour.