Continuous Switch Model and Heuristics for Mixed-Integer Problems in Power Systems

Aayushya Agarwal, Amritanshu Pandey, Marko Jereminov, Larry PillegiarXiv 2022 · DOI · OpenReview

TL;DR

This paper introduces GISMO, a novel framework that transforms complex power system optimization problems (MINLP) into continuous, solvable NLP problems by modeling binary switch decisions with a circuit-based continuous switch. This approach, coupled with physics-driven heuristics, enables robust and scalable solutions for large-scale power grids, guaranteeing AC-feasible optima, a significant improvement over existing methods.

What Problem Does This Paper Address?

Power system operations and planning often involve deciding whether to connect or disconnect grid components (like transmission lines or generators). These decisions are typically modeled as mixed-integer nonlinear programming (MINLP) problems, where binary variables represent these on/off states. The challenge is that these binary variables, combined with the nonlinear AC network constraints, make the problem NP-hard. For real-world, large-scale power grids, finding an optimal solution that also satisfies AC feasibility (i.e., adheres to physical laws of power flow) is computationally prohibitive with current tools. Existing methods either linearize AC constraints (leading to non-AC-feasible solutions) or relax binary variables (leading to difficult-to-solve, non-convex NLPs that struggle with scalability). This paper aims to bridge this gap by providing a method that directly yields AC-feasible, optimal solutions for large-scale power system optimization problems.

Methods

The core innovation is the Continuous Switch Model for representing binary decisions. Instead of a discrete 0 or 1, binary variables are modeled as a continuous switch conductance, $G_{sw}$, that can vary between 0 and a large value ($G_{closed}$). This conductance is controlled by a "driving mechanism" ($V_g$) that mimics the physical behavior of a real-world switch. This circuit-inspired model transforms the MINLP into a fully continuous NLP.

To handle the inherent non-convexities and ensure robust convergence in large systems, the authors developed two key physics-driven heuristics:

  1. Path-tracing Homotopy Methods: Inspired by circuit simulation, these methods solve a series of progressively complex sub-problems, starting from a simple, convex problem and gradually leading to the original, complex problem. This approach avoids abrupt changes in the solution space. Specifically, they augment the Incremental Model Building (IMB) homotopy method with:
  2. Gmin Stepping: This method introduces a shunt conductance that effectively shorts companion circuit nodes, forcing switch conductances to zero initially and then gradually reducing the shunt conductance. This helps in starting from a trivial solution and avoids abrupt changes in switch states.
  3. Parallel Conductance Stepping: This method inserts a parallel conductance to the nonlinear switch conductance to prevent large voltage changes when switches close, ensuring smoother transitions and maintaining quadratic convergence.
  4. Newton-Raphson Damping: The steep current-voltage relationship of the continuous switch model can cause numerical oscillations in gradient-based solvers like Newton-Raphson. This heuristic dampens the update steps in NR to prevent large changes in the switch conductance, ensuring it stays within bounds and avoids divergence.

Datasets

The paper evaluates its approach on:

  • A small, 14-bus IEEE test case for initial validation.
  • A modified synthetic US Eastern Interconnection test case with approximately 70,000 buses, used to demonstrate scalability. This test case is based on real-world data and is modified to include renewable energy integration challenges.

Key Insights and Ideas

  • Physical Analogy for Binary Variables: Representing binary decisions as a continuous, circuit-like switch provides a more intuitive and physically grounded approach than abstract mathematical relaxations. This allows leveraging well-established circuit simulation techniques.
  • Guaranteed AC Feasibility: By transforming the problem into an NLP that inherently respects AC network constraints, the method guarantees that the obtained optimal solutions are physically realistic and operational. This is a major advantage over DC-based relaxations.
  • Scalability through Heuristics: The combination of homotopy methods and NR damping is crucial for scaling to large, realistic power grids. These heuristics are designed to exploit the physics of the problem, ensuring robust convergence where standard methods fail.
  • Tight Relaxation Bounds: The paper mathematically shows that the continuous switch model is a tight relaxation of the original MINLP, providing theoretical guarantees on the quality of the solutions.

Key Results

  • The GISMO framework successfully solves large-scale power system optimization problems (up to 70,000 buses) in practical wall-clock times.
  • It consistently finds AC-feasible optimal solutions, outperforming industry-standard MINLP solvers like KNITRO and Gurobi (when used with DC approximations) which either fail to converge or produce infeasible solutions for AC constraints.
  • For the 14-bus test case, GISMO identified an optimal configuration of generators and transmission lines that matched results from brute-force analysis (for a subset of configurations) and outperformed other relaxation methods.
  • In scalability tests on the Eastern Interconnection, GISMO demonstrated robust convergence with flat start initial conditions, while fmincon (a standard NLP solver) failed to converge. When initialized with GISMO's solution, fmincon converged rapidly.

Limitations and Future Work

  • Computational Cost: While scalable, solving these large-scale problems still requires significant computational resources. The paper mentions that the "fast-start" generator problem was solved for a single time-window, implying that extending to multiple time steps (as in full unit commitment) would increase complexity.
  • Heuristic Tuning: The effectiveness of the homotopy and damping methods might depend on parameter tuning, although the paper suggests some values work well.
  • Future Work: The authors suggest that GISMO can be applied to a wider range of power system analyses, including generation expansion, transmission switching, and unit commitment, particularly in scenarios with high renewable penetration. The framework's ability to handle AC constraints makes it suitable for future grid modernization studies.

Summary updated

Abstract

Many power systems operation and planning computations (e.g., transmission and generation switching and placement) solve a mixed-integer nonlinear problem (MINLP) with binary variables representing the decision to connect devices to the grid. Binary variables with nonlinear AC network constraints make this problem NP-hard. For large real-world networks, obtaining an AC feasible optimum solution for these problems is computationally challenging and often unattainable with state-of-the-art tools today. In this work, we map the MINLP decision problem into a set of equivalent circuits by representing binary variables with a circuit-based continuous switch model. We characterize the continuous switch model by a controlled nonlinear impedance that more closely mimics the physical behavior of a real-world switch. This mapping effectively transforms the MINLP problem into an NLP problem. We mathematically show that this transformation is a tight relaxation of the MINLP problem. For fast and robust convergence, we develop physics-driven homotopy and Newton-Raphson damping methods. To validate this approach, we empirically show robust convergences for large, realistic systems ($>$ 70,000 buses) in a practical wall-clock time to an AC-feasible optimum. We compare our results and show improvement over industry-standard tools and other binary relaxation methods.
BibTeX
@misc{agarwal2022continuous,
  author = {Aayushya Agarwal and Amritanshu Pandey and Marko Jereminov and Larry Pillegi},
  title = {{Continuous Switch Model and Heuristics for Mixed-Integer Problems in Power Systems}},
  year = {2022},
  eprint = {2206.14510},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2206.14510},
}
Figure