The Complexity of DC-Switching Problems

Abstract

This report provides a comprehensive complexity study of line switching in the Linear DC model for the feasibility problem and the optimization problems of maximizing the load that can be served (maximum switching flow, MSF) and minimizing generation cost (optimal transmission switching, OTS). Our results show that these problems are NP-complete and that there is no fully polynomial-time approximation scheme for planar networks with a maximum-node degree of 3. Additionally, we demonstrate that the problems are still NP-hard if we restrict the network structure to cacti with a maximum degree of 3. We also show that the optimization problems can not be approximated within any constant factor.

Cited by in corpus (5)

• A Cycle-Based Formulation and Valid Inequalities for DC Power Transmission Problems with Switching
• Optimal Transmission Topology for Facilitating the Growth of Renewable Power Generation
• Node-based valid inequalities for the optimal transmission switching problem
• A K-Nearest Neighbor Heuristic for Real-Time DC Optimal Transmission Switching
• Data-driven Heuristics for DC optimal transmission switching problem