Virtual-Voltage Partition-Based Approach to Optimal Transmission Switching

Chin-Yao Chang, Sonia Martínez, Jorge CortésIEEE Trans. Control. Syst. Technol 2021 · OpenReview

TL;DR

This paper tackles the complex problem of optimizing electricity transmission network topology (Optimal Transmission Switching - OTS) by introducing a novel "virtual-voltage" approximation to handle non-convexities in power flow equations. They then combine this with a graph partitioning algorithm to break down the problem into smaller, parallelizable subproblems, significantly improving computational efficiency.

What Problem Does This Paper Address?

The core challenge is finding the most cost-effective way to configure electricity grids by deciding which transmission lines to switch on or off. This "Optimal Transmission Switching" (OTS) problem is notoriously difficult because it involves:

  1. Discrete Decisions: Whether a transmission line is "on" or "off" is a binary (0 or 1) decision.
  2. Non-Convex Power Flow: The physics of how electricity flows through a network (described by AC Optimal Power Flow - ACOPF) are inherently non-linear and non-convex, making them hard to solve mathematically.
  3. Bilinear Terms: The interaction between the discrete switching decisions and the continuous power flow variables creates "bilinear terms," which are a major source of non-convexity.

Traditional methods like linearized power flow (DCOPF) are fast but inaccurate, while full ACOPF solvers are accurate but computationally prohibitive. Existing approaches using semidefinite programming (SDP) relaxations can handle some non-convexities but struggle with the combination of discrete variables and bilinear terms. This paper aims to bridge this gap by providing a more accurate and computationally feasible method for solving OTS problems.

Methods

The authors propose a two-pronged approach:

  1. Virtual-Voltage Approximation: This is the core innovation for handling the bilinear terms. Instead of directly dealing with the product of discrete switch variables and continuous voltage variables, they introduce "virtual-voltage" variables for the endpoints of switchable lines. These virtual voltages are constrained to be physically meaningful and are linked to the overall network state (represented by a matrix W in the SDP formulation). This approach provides provable lower and upper bounds on the solution.
  2. Graph Partition-Based Algorithm: To address the exponential complexity arising from the discrete switching decisions, they employ a graph partitioning strategy.
  3. Graph Reduction: They first "collapse" nodes connected by switchable lines into single representative nodes. This ensures that switchable lines don't end up in different subproblems, which would break the physical coupling.
  4. Spectral Graph Partitioning: They use the dual variables from the virtual-voltage SDP solution to assign weights to edges in the reduced graph. Then, they apply spectral graph partitioning to divide the network into smaller, interconnected subgraphs. The goal is to minimize the "cut" (removed edges) between these subgraphs, effectively minimizing the correlation between their optimal solutions.
  5. Parallel Subproblem Solving: Each subgraph is then solved as a smaller mixed-integer optimization problem.
  6. Reconstruction: Finally, the solutions from the subproblems are combined, and a full SDP optimization is performed with the determined switch configurations to reconstruct the overall optimal solution.

Datasets

The paper evaluates their approach on standard IEEE test systems: IEEE 30, IEEE 39, IEEE 57, IEEE 89, IEEE 118, and IEEE 300 bus systems. They do not introduce new datasets or benchmarks.

Key Insights and Ideas

  • Virtual Voltages as a Bridge: The virtual-voltage concept is a clever way to approximate the complex interactions of discrete switches and continuous power flows by imposing physically-inspired constraints on auxiliary voltage variables. This allows for provable bounds, a significant improvement over ad-hoc relaxations.
  • Graph Partitioning for Scalability: Breaking down a large, complex optimization problem into smaller, parallelizable subproblems is a common strategy for improving computational efficiency. The novelty here is using the dual variables from the SDP relaxation to guide the partitioning, ensuring that the subproblems are structured to better reflect the original problem's dependencies.
  • Trade-off Between Accuracy and Speed: The virtual-voltage approach, while more computationally intensive than simpler relaxations like McCormick, offers significantly better accuracy. The partition-based algorithm further enhances speed by enabling parallel computation.
  • Limitations of General Solvers: The paper highlights that general-purpose solvers like BARON struggle with the specific structure of OTS problems (discrete variables, non-convexities, bilinear terms), underscoring the need for specialized methods.

Key Results

  • Improved Accuracy: The virtual-voltage approximation consistently provides better solutions (lower bounds) compared to the McCormick relaxation, especially when using tighter bounds for the latter.
  • Computational Efficiency: The partition-based algorithm significantly reduces computation time, especially for larger test cases, by enabling parallel processing of subproblems. For instance, on the IEEE 300 bus system with all lines switchable, their method takes hours, whereas a QC relaxation method takes 10 hours on thousands of CPUs.
  • Feasible Solutions: The proposed method reliably finds feasible solutions, whereas other methods (like BARON or McCormick with certain bounds) sometimes fail to converge.
  • Rank-1 Solutions: For cases with a moderate number of switchable lines (e.g., 40), the SDP relaxation often yields rank-1 solutions, which are desirable as they directly correspond to a physical network state.

Limitations and Future Work

  • N-1 Security Constraints: While the virtual-voltage approach can be extended to N-1 security constraints (ensuring grid stability under single component failures), the computational cost increases significantly, making it less practical for large systems.
  • Rank of SDP Solutions: For cases with all lines switchable, the SDP relaxation might produce high-rank solutions for the W matrix, meaning it's not a perfect representation of a single physical state. However, the authors note that the condition number is still high enough to imply good accuracy.
  • Future Work: The authors suggest exploring distributed methods and incorporating other types of discrete controls into their framework. They also aim to investigate distributed methods for general mixed-integer OPF problems.

Summary updated

Abstract

This article deals with optimal transmission switching (OTS) problems involving binary decisions about network topology and nonconvex power flow constraints. We adopt a semidefinite programming formulation for the optimal power flow (OPF) problem that, however, remains nonconvex due to the presence of discrete variables and bilinear products between the decision variables. To tackle the latter, we introduce a physically inspired, virtual-voltage approximation that leads to provable lower and upper bounds on the solution of the original problem. To deal with the exponential complexity caused by the discrete variables, we introduce a graph partition-based algorithm that breaks the problem into several parallel mixed-integer subproblems of smaller size. Simulations on the IEEE bus test cases demonstrate the high degree of accuracy and affordable computational requirements of our approach.
BibTeX
@article{chang2021virtual,
  author = {Chin-Yao Chang and Sonia Martínez and Jorge Cortés},
  title = {{Virtual-Voltage Partition-Based Approach to Optimal Transmission Switching}},
  journal = {IEEE Trans. Control. Syst. Technol.},
  year = {2021},
  url = {https://openreview.net/forum?id=rB32AUnXZf},
}
Figure