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

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 U.S. 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 give 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, and the 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.

References in corpus (1)

• The Complexity of DC-Switching Problems

Cited by in corpus (11)

• New Formulation and Strong MISOCP Relaxations for AC Optimal Transmission Switching Problem
• Linear Optimal Power Flow Using Cycle Flows
• A Repeated Route-then-Schedule Approach to Coordinated Vehicle Platooning: Algorithms, Valid Inequalities and Computation
• Node-based valid inequalities for the optimal transmission switching problem
• Real-Time Contingency Analysis with Corrective Transmission Switching - Part I: Methodology
• A K-Nearest Neighbor Heuristic for Real-Time DC Optimal Transmission Switching
• Data-driven Heuristics for DC optimal transmission switching problem
• New Cycle-based Formulation, Cost Function, and Heuristics for DC OPF Based Controlled Islanding
• Transmission Expansion Planning Using Cycle Flows
• Polynomial-time algorithms for setting tight big-M coefficients in transmission expansion planning with disconnected buses
• Tightening Quadratic Convex Relaxations for the AC Optimal Transmission Switching Problem