Optimizing electric grid design under asymmetric threat (II)

Abstract

This research extends our earlier work to improve the security of electric power grids subject to disruptions caused by terrorist attacks. To identify critical system components (e.g., transmission lines, generators, transformers), we devise bilevel optimization models that identify maximally disruptive attack plans for terrorists, who are assumed to have limited offensive resources. A new model captures the dynamics of system operation as a network is repaired after an attack, and we adapt an earlier heuristic for that model's solution. We also develop a new, mixed-integer programming model (MIP) for the problem; a model that can be solved exactly using standard optimization software, at least in theory. Preliminary testing shows that optimal solutions are readily achieved for certain standard test problems, although not for the largest ones, which the heuristic seems to handle well. However, optimal solutions do provide a benchmark to measure the accuracy of the heuristic: The heuristic typically achieves optimality gaps of less than 10%, but occasionally the gap reaches 25%. Research will continue to refine the heuristic algorithm, the MIP formulation, and the algorithms to solve it. We also demonstrate progress made towards a graphical user interface that allows performing our interdiction analysis in a friendly environment.