IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v34y2022i4p2296-2312.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Emma S. Johnson & Santanu Subhas Dey, 2022. "A Scalable Lower Bound for the Worst-Case Relay Attack Problem on the Transmission Grid," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2296-2312, July.
  • Handle: RePEc:inm:orijoc:v:34:y:2022:i:4:p:2296-2312
    DOI: 10.1287/ijoc.2022.1178
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.1178
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2022.1178?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Smith, J. Cole & Song, Yongjia, 2020. "A survey of network interdiction models and algorithms," European Journal of Operational Research, Elsevier, vol. 283(3), pages 797-811.
    2. Burak Kocuk & Hyemin Jeon & Santanu S. Dey & Jeff Linderoth & James Luedtke & Xu Andy Sun, 2016. "A Cycle-Based Formulation and Valid Inequalities for DC Power Transmission Problems with Switching," Operations Research, INFORMS, vol. 64(4), pages 922-938, August.
    3. Seth Blumsack & Lester B. Lave & Marija Ilic, 2007. "A Quantitative Analysis of the Relationship Between Congestion and Reliability in Electric Power Networks," The Energy Journal, , vol. 28(4), pages 73-100, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Cerulli, Martina & Serra, Domenico & Sorgente, Carmine & Archetti, Claudia & Ljubić, Ivana, 2023. "Mathematical programming formulations for the Collapsed k-Core Problem," European Journal of Operational Research, Elsevier, vol. 311(1), pages 56-72.
    2. Benjamin, Richard, 2013. "A two-part tariff for financing transmission expansion," Utilities Policy, Elsevier, vol. 27(C), pages 98-107.
    3. Juan Rosellón & Hannes Weigt, 2011. "A Dynamic Incentive Mechanism for Transmission Expansion in Electricity Networks: Theory, Modeling, and Application," The Energy Journal, , vol. 32(1), pages 119-148, January.
    4. Beck, Yasmine & Ljubić, Ivana & Schmidt, Martin, 2023. "A survey on bilevel optimization under uncertainty," European Journal of Operational Research, Elsevier, vol. 311(2), pages 401-426.
    5. Blumsack, Seth & Xu, Jianhua, 2011. "Spatial variation of emissions impacts due to renewable energy siting decisions in the Western U.S. under high-renewable penetration scenarios," Energy Policy, Elsevier, vol. 39(11), pages 6962-6971.
    6. Skolfield, J. Kyle & Escobedo, Adolfo R., 2022. "Operations research in optimal power flow: A guide to recent and emerging methodologies and applications," European Journal of Operational Research, Elsevier, vol. 300(2), pages 387-404.
    7. Guanglei Wang & Hassan Hijazi, 2018. "Mathematical programming methods for microgrid design and operations: a survey on deterministic and stochastic approaches," Computational Optimization and Applications, Springer, vol. 71(2), pages 553-608, November.
    8. Luis M. Abadie & José M. Chamorro, 2011. "Valuing Expansions of the Electricity Transmission Network under Uncertainty: The Binodal Case," Energies, MDPI, vol. 4(10), pages 1-32, October.
    9. Ashraf, Muhammad Hasan & Chen, Yuwen & Yalcin, Mehmet G., 2022. "Minding Braess Paradox amid third-party logistics hub capacity expansion triggered by demand surge," International Journal of Production Economics, Elsevier, vol. 248(C).
    10. Avci, Mualla Gonca & Avci, Mustafa & Battarra, Maria & Erdoğan, Güneş, 2024. "The wildfire suppression problem with multiple types of resources," European Journal of Operational Research, Elsevier, vol. 316(2), pages 488-502.
    11. Fränk Plein & Johannes Thürauf & Martine Labbé & Martin Schmidt, 2022. "A bilevel optimization approach to decide the feasibility of bookings in the European gas market," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 95(3), pages 409-449, June.
    12. Nguyen, Kien Trung & Hung, Nguyen Thanh, 2021. "The minmax regret inverse maximum weight problem," Applied Mathematics and Computation, Elsevier, vol. 407(C).
    13. Hunt, Kyle & Zhuang, Jun, 2024. "A review of attacker-defender games: Current state and paths forward," European Journal of Operational Research, Elsevier, vol. 313(2), pages 401-417.
    14. Carayannis, Elias G. & Grigoroudis, Evangelos & Wurth, Bernd, 2022. "OR for entrepreneurial ecosystems: A problem-oriented review and agenda," European Journal of Operational Research, Elsevier, vol. 300(3), pages 791-808.
    15. William Hogan & Juan Rosellón & Ingo Vogelsang, 2010. "Toward a combined merchant-regulatory mechanism for electricity transmission expansion," Journal of Regulatory Economics, Springer, vol. 38(2), pages 113-143, October.
    16. Cheung, Kam-Fung & Bell, Michael G.H., 2021. "Improving connectivity of compromised digital networks via algebraic connectivity maximisation," European Journal of Operational Research, Elsevier, vol. 294(1), pages 353-364.
    17. Bloch, Francis & Chatterjee, Kalyan & Dutta, Bhaskar, 2023. "Attack and interception in networks," Theoretical Economics, Econometric Society, vol. 18(4), November.
    18. Eric DuBois & Ashley Peper & Laura A. Albert, 2023. "Interdicting Attack Plans with Boundedly Rational Players and Multiple Attackers: An Adversarial Risk Analysis Approach," Decision Analysis, INFORMS, vol. 20(3), pages 202-219, September.
    19. Wei, Ningji & Walteros, Jose L., 2022. "Integer programming methods for solving binary interdiction games," European Journal of Operational Research, Elsevier, vol. 302(2), pages 456-469.
    20. J. Kyle Skolfield & Laura M. Escobar & Adolfo R. Escobedo, 2022. "Derivation and generation of path-based valid inequalities for transmission expansion planning," Annals of Operations Research, Springer, vol. 312(2), pages 1031-1049, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:34:y:2022:i:4:p:2296-2312. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.