IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v64y2016i4p922-938.html
   My bibliography  Save this article

A Cycle-Based Formulation and Valid Inequalities for DC Power Transmission Problems with Switching

Author

Listed:
  • Burak Kocuk

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • Hyemin Jeon

    (Department of Industrial Engineering and Operations Research, University of California, Berkeley, Berkeley, California 94720)

  • Santanu S. Dey

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • Jeff Linderoth

    (Department of Industrial and Systems Engineering, University of Wisconsin-Madison, Madison, Wisconsin 53706)

  • James Luedtke

    (Department of Industrial and Systems Engineering, University of Wisconsin-Madison, Madison, Wisconsin 53706)

  • Xu Andy Sun

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

Abstract

It is well known that optimizing network topology by switching on and off transmission lines improves the efficiency of power delivery in electrical networks. In fact, the USA Energy Policy Act of 2005 (Section 1223) states that the United States should “encourage, as appropriate, the deployment of advanced transmission technologies” including “optimized transmission line configurations.” As such, many authors have studied the problem of determining an optimal set of transmission lines to switch off to minimize the cost of meeting a given power demand under the direct current (DC) model of power flow. This problem is known in the literature as the Direct-Current Optimal Transmission Switching Problem (DC-OTS). Most research on DC-OTS has focused on heuristic algorithms for generating quality solutions or on the application of DC-OTS to crucial operational and strategic problems such as contingency correction, real-time dispatch, and transmission expansion. The mathematical theory of the DC-OTS problem is less well developed. In this work, we formally establish that DC-OTS is NP-Hard, even if the power network is a series-parallel graph with at most one load/demand pair. Inspired by Kirchoff’s Voltage Law, we provide a cycle-based formulation for DC-OTS, and we use the new formulation to build a cycle-induced relaxation. We characterize the convex hull of the cycle-induced relaxation; this characterization provides strong valid inequalities that can be used in a cutting-plane approach to solve the DC-OTS. We give details of a practical implementation, and we show promising computational results on standard benchmark instances.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:oropre:v:64:y:2016:i:4:p:922-938
    DOI: 10.1287/opre.2015.1471
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2015.1471
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2015.1471?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. FERREIRA, C. E. & MARTIN, A. & de SOUZA, C. C. & WEISMANTEL, R., 1996. "Formulations and valid inequalities for the node capacitated graph partitioning problem," LIDAM Reprints CORE 1236, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Mathieu Van Vyve, 2005. "The Continuous Mixing Polyhedron," Mathematics of Operations Research, INFORMS, vol. 30(2), pages 441-452, May.
    3. Villumsen, J.C. & Philpott, A.B., 2012. "Investment in electricity networks with transmission switching," European Journal of Operational Research, Elsevier, vol. 222(2), pages 377-385.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. 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.
    2. Selvaprabu Nadarajah & Andre A. Cire, 2020. "Network-Based Approximate Linear Programming for Discrete Optimization," Operations Research, INFORMS, vol. 68(6), pages 1767-1786, November.
    3. 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.
    4. 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.
    5. Märkle-Huß, Joscha & Feuerriegel, Stefan & Neumann, Dirk, 2020. "Cost minimization of large-scale infrastructure for electricity generation and transmission," Omega, Elsevier, vol. 96(C).
    6. Pedro Pablo Cardenas Alzate & Laura Monica Escobar Vargas & Antonio Hernando Escobar Zuluaga, 2019. "Planning the Expansion of Long-Term Transmission Networks Using a Cycle-Based Formulation," Modern Applied Science, Canadian Center of Science and Education, vol. 13(1), pages 237-237, January.
    7. David Bergman & Andre A. Cire, 2018. "Discrete Nonlinear Optimization by State-Space Decompositions," Management Science, INFORMS, vol. 64(10), pages 4700-4720, October.
    8. 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.

    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. Michele Conforti & Gérard Cornuéjols & Giacomo Zambelli, 2013. "Extended formulations in combinatorial optimization," Annals of Operations Research, Springer, vol. 204(1), pages 97-143, April.
    2. W. David Pisinger & Anders Bo Rasmussen & Rune Sandvik, 2007. "Solution of Large Quadratic Knapsack Problems Through Aggressive Reduction," INFORMS Journal on Computing, INFORMS, vol. 19(2), pages 280-290, May.
    3. DI SUMMA, Marco & WOLSEY, Laurence, 2010. "Mixing sets linked by bidirected paths," LIDAM Discussion Papers CORE 2010063, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. Yongjia Song & Minjiao Zhang, 2015. "Chance‐constrained multi‐terminal network design problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(4), pages 321-334, June.
    5. John E. Mitchell, 2003. "Realignment in the National Football League: Did they do it right?," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(7), pages 683-701, October.
    6. Huppmann, Daniel & Egerer, Jonas, 2015. "National-strategic investment in European power transmission capacity," European Journal of Operational Research, Elsevier, vol. 247(1), pages 191-203.
    7. Jabarnejad, Masood & Valenzuela, Jorge, 2016. "Optimal investment plan for dynamic thermal rating using benders decomposition," European Journal of Operational Research, Elsevier, vol. 248(3), pages 917-929.
    8. Michael M. Sørensen, 2004. "b-Tree Facets for the Simple Graph Partitioning Polytope," Journal of Combinatorial Optimization, Springer, vol. 8(2), pages 151-170, June.
    9. Fang, Yiping & Sansavini, Giovanni, 2017. "Optimizing power system investments and resilience against attacks," Reliability Engineering and System Safety, Elsevier, vol. 159(C), pages 161-173.
    10. Michele Conforti & Marco Di Summa & Friedrich Eisenbrand & Laurence A. Wolsey, 2009. "Network Formulations of Mixed-Integer Programs," Mathematics of Operations Research, INFORMS, vol. 34(1), pages 194-209, February.
    11. CONFORTI, Michele & DI SUMMA, Marco & EISENBRAND, Fritz & WOLSEY, Laurence A., 2006. "Network formulations of mixed-integer programs," LIDAM Discussion Papers CORE 2006117, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    12. C. Helmberg & F. Rendl & R. Weismantel, 2000. "A Semidefinite Programming Approach to the Quadratic Knapsack Problem," Journal of Combinatorial Optimization, Springer, vol. 4(2), pages 197-215, June.
    13. Minjiao Zhang & Simge Küçükyavuz & Saumya Goel, 2014. "A Branch-and-Cut Method for Dynamic Decision Making Under Joint Chance Constraints," Management Science, INFORMS, vol. 60(5), pages 1317-1333, May.
    14. Anuj Mehrotra & Joseph Shantz & Michael A. Trick, 2005. "Determining newspaper marketing zones using contiguous clustering," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(1), pages 82-92, February.
    15. Jonas Christoffer Villumsen & Joe Naoum‐Sawaya, 2016. "Column generation for stochastic green telecommunication network planning with switchable base stations," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(5), pages 351-366, August.
    16. Araújo, Paulo H. M. & Campêlo, Manoel & Corrêa, Ricardo C. & Labbé, Martine, 2024. "Integer programming models and polyhedral study for the geodesic classification problem on graphs," European Journal of Operational Research, Elsevier, vol. 314(3), pages 894-911.
    17. Pichler, Alois & Tomasgard, Asgeir, 2016. "Nonlinear stochastic programming–With a case study in continuous switching," European Journal of Operational Research, Elsevier, vol. 252(2), pages 487-501.
    18. Ruiz, C. & Conejo, A.J., 2015. "Robust transmission expansion planning," European Journal of Operational Research, Elsevier, vol. 242(2), pages 390-401.
    19. Moreira, Alexandre & Pozo, David & Street, Alexandre & Sauma, Enzo & Strbac, Goran, 2021. "Climate‐aware generation and transmission expansion planning: A three‐stage robust optimization approach," European Journal of Operational Research, Elsevier, vol. 295(3), pages 1099-1118.
    20. Märkle-Huß, Joscha & Feuerriegel, Stefan & Neumann, Dirk, 2020. "Cost minimization of large-scale infrastructure for electricity generation and transmission," Omega, Elsevier, vol. 96(C).

    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:oropre:v:64:y:2016:i:4:p:922-938. 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.