Optimization Strategies for the Vulnerability Analysis of the Electric Power Grid

TLDR

Identifying small groups of lines whose removal would cause a severe blackout is critical for the secure operation of the electric power grid. The study demonstrates that power grid vulnerability analysis can be framed as a bilevel mixed integer nonlinear programming problem. The authors formulate the vulnerability analysis as a bilevel mixed integer nonlinear programming problem and then reduce it to a network inhibition problem solvable via a mixed integer linear programming formulation. The analysis uncovers a special structure linking the Jacobian matrix to the Laplacian matrix, enabling the nonlinear problem to be approximated as a pure combinatorial problem, and experiments on benchmark grids confirm that this reduced model accurately approximates the original problem, allowing vulnerability analyses of grids with over 16,520 lines.

Abstract

Identifying small groups of lines, whose removal would cause a severe blackout, is critical for the secure operation of the electric power grid. We show how power grid vulnerability analysis can be studied as a bilevel mixed integer nonlinear programming problem. Our analysis reveals a special structure in the formulation that can be exploited to avoid nonlinearity and approximate the original problem as a pure combinatorial problem. The key new observation behind our analysis is the correspondence between the Jacobian matrix (a representation of the feasibility boundary of the equations that describe the flow of power in the network) and the Laplacian matrix in spectral graph theory (a representation of the graph of the power grid). The reduced combinatorial problem is known as the network inhibition problem, for which we present a mixed integer linear programming formulation. Our experiments on benchmark power grids show that the reduced combinatorial model provides an accurate approximation, to enable vulnerability analyses of real-sized problems with more than 16,520 power lines.