A Scalable Lower Bound for the Worst-Case Relay Attack Problem on the Transmission Grid

We consider a bilevel attacker–defender problem to find the worst-case attack on the relays that control transmission grid components. The attacker infiltrates some number of relays and renders all of the components connected to them inoperable with the goal of maximizing load shed. The defender responds by minimizing the resulting load shed, redispatching using a DC optimal power flow (DCOPF) problem on the remaining network. Though worst-case interdiction problems on the transmission grid have been studied for years, there remains a need for exact and scalable methods. Methods based on using duality on the inner problem rely on the bounds of the dual variables of the defender problem in order to reformulate the bilevel problem as a mixed integer linear problem. Valid dual bounds tend to be large, resulting in weak linear programming relaxations and, hence, making the problem more difficult to solve at scale. Often smaller heuristic bounds are used, resulting in a lower bound. In this work, we also consider a lower bound, but instead of bounding the dual variables, we drop the constraints corresponding to Ohm’s law, relaxing DCOPF to capacitated network flow. We present theoretical results showing that, for uncongested networks, approximating DCOPF with network flow yields the same set of injections and, thus, the same load shed, which suggests that this restriction likely gives a high-quality lower bound in the uncongested case. Furthermore, we show that, in the network flow relaxation of the defender problem, the duals are bounded by one, so we can solve our restriction exactly. Finally, because the big-M values in the linearization are equal to one and network flow has a well-known structure, we see empirically that this formulation scales well computationally with increased network size. Through empirical experiments on 16 networks with up to 6,468 buses, we find that this bound is almost always as tight as we can get from guessing the dual bounds even for congested networks in which the theoretical results do not hold. In addition, calculating the bound is approximately 150 times faster than achieving the same bound with the reformulation guessing the dual bounds.