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

Burak Kocuk, Hyemin Jeon, Santanu S. Dey, Jeff T. Linderoth, James R. Luedtke, Xu Andy SunOper. res 2016 · DOI

TL;DR

This paper introduces a novel cycle-based formulation for the Direct Current Optimal Transmission Switching (DC-OTS) problem, a crucial aspect of optimizing power grid operations. By deriving strong valid inequalities from this formulation, the authors significantly improve the performance of standard optimization solvers, leading to faster and more efficient solutions for complex power transmission planning.

What Problem Does This Paper Address?

Electric power grids are complex systems where optimizing the flow of electricity is paramount for efficiency and reliability. A key challenge is determining which transmission lines to switch on or off to meet demand at the minimum cost. This is known as the Optimal Transmission Switching (OTS) problem. While the Direct Current (DC) approximation of power flow is widely used in industry for its simplicity, existing mathematical models for DC-OTS often lead to computationally intractable problems due to weak linear relaxations. This means that standard optimization solvers struggle to find optimal solutions efficiently. The authors aim to address this by developing a more theoretically grounded and computationally effective approach to solving the DC-OTS problem.

Methods

The paper's core contribution lies in a new "cycle-based formulation" for the DC-OTS problem. Instead of relying on the traditional angle-based formulation, they leverage Kirchhoff's Voltage Law (KVL) applied to cycles within the power network. This approach leads to a relaxation of the problem that can be characterized by a set of "valid inequalities." These inequalities are derived from the convex hull of this cycle-induced relaxation. The authors then develop algorithms to efficiently separate these inequalities, meaning they can be added as "cuts" to the optimization problem to strengthen its linear relaxation. This "cut-and-branch" approach, where cuts are iteratively added to improve the problem's tractability, is then integrated with a commercial Mixed-Integer Programming (MIP) solver (CPLEX).

Datasets

The authors generated several sets of test instances based on existing power network models:

  • case118B: A 118-bus network from Blumsack (2006).
  • case300: A 300-bus network.

These base instances were modified to create five specific test sets:

  • Set 118_15: Increased load on case118B.
  • Set 118_15_6: Added 6-cycles to Set 118_15.
  • Set 118_15_16: Added 16-cycles to Set 118_15.
  • Set 118_9G: Modified loads and generator locations on case118B.
  • Set 300-5: Modified loads, turned off generators, and adjusted costs/limits on case300.

Key Insights and Ideas

  • DC-OTS is NP-Hard, even for simple networks: The paper formally proves that the DC-OTS problem remains NP-Hard even for series-parallel graphs with a single load/demand pair. This highlights the inherent computational difficulty of the problem.
  • Cycles offer a new perspective: By reformulating the problem using cycles and Kirchhoff's Voltage Law, the authors unlock a new way to understand and model the DC-OTS problem, moving beyond traditional angle-based approaches.
  • Stronger inequalities lead to better performance: The derived cycle-based inequalities are shown to be "strong," meaning they significantly tighten the linear relaxation of the problem. This directly translates to improved performance for MIP solvers.
  • "Few lines off" can yield significant benefits: The sensitivity analysis reveals that substantial cost savings can often be achieved by switching off only a small number of transmission lines, suggesting that optimal solutions might not always require drastic network reconfigurations.

Key Results

The computational experiments demonstrate the effectiveness of the proposed cycle-based inequalities.

  • The "MoreCycles" algorithm, which uses inequalities from a larger set of cycles, consistently outperformed the default CPLEX solver and a baseline approach using only a cycle basis.
  • Specifically, "MoreCycles" achieved significant reductions in the size of the Branch-and-Bound tree, total computation time, and the number of unsolved instances.
  • For instance, on average, the "MoreCycles" approach closed a higher percentage of the integrality gap at the root node and solved instances much faster than the default method.
  • The performance profiles show that while the "BasicCycles" approach was often the fastest on individual instances, "MoreCycles" solved the most instances within the time limit, indicating better robustness.

Limitations and Future Work

  • Complexity of generating cycles: While the cycle-based inequalities are effective, generating a comprehensive set of cycles for large networks can be computationally expensive. The paper uses a cycle basis and then generates additional cycles, but further research into efficient cycle generation for very large-scale networks is suggested.
  • DC approximation limitations: The paper acknowledges that the DC approximation of power flow has limitations and may not accurately capture all aspects of AC power flow for certain problems. Future work could explore extending these ideas to AC-OTS.
  • Nonlinear objective functions: The current formulation assumes a linear generation cost. The authors note that their inequalities might still be useful for convex quadratic cost functions, but further investigation into their applicability for more general nonlinear objectives is warranted.
  • Flow balance constraints: The current cycle-induced relaxation does not explicitly include flow balance constraints. The authors suggest that incorporating these could lead to even stronger relaxations.

Summary updated

BibTeX
@article{kocuk2016cycle,
  author = {Burak Kocuk and Hyemin Jeon and Santanu S. Dey and Jeff T. Linderoth and James R. Luedtke and Xu Andy Sun},
  title = {{A Cycle-Based Formulation and Valid Inequalities for DC Power Transmission Problems with Switching}},
  journal = {Oper. res},
  year = {2016},
  doi = {10.1287/opre.2015.1471},
}
Figure