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

Emma S. Johnson () and Santanu Subhas Dey ()
Additional contact information
Emma S. Johnson: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332; Sandia National Laboratories, Albuquerque, New Mexico 87185
Santanu Subhas Dey: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332

INFORMS Journal on Computing, 2022, vol. 34, issue 4, 2296-2312

Abstract: 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.

Keywords: bilevel programming; interdiction; mixed integer programming (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1178 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:4:p:2296-2312

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().