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

Burak Kocuk (), Hyemin Jeon (), Santanu S. Dey (), Jeff Linderoth (), James Luedtke () and Xu Andy Sun ()
Additional contact information
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

Operations Research, 2016, vol. 64, issue 4, 922-938

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.

Keywords: integer programming; cutting plane/facets; electric industries (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2015.1471 (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:oropre:v:64:y:2016:i:4:p:922-938

Access Statistics for this article

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