Facet-Defining Inequalities for the Angle-Based DC Optimal Transmission Switching Formulation

This paper challenges the prevailing view that tightening voltage angle bounds in the Direct-Current Optimal Transmission Switching problem requires solving an intractable longest path problem by presenting a novel polyhedral analysis that derives facet-defining inequalities to construct an extended formulation for the convex hull of the angle-based relaxation.

The Gist

Imagine a massive, complex city of electricity called the Power Grid. In this city, electricity travels along roads called transmission lines connecting different neighborhoods (buses). The goal of the city planners is to keep the lights on for everyone while spending the absolute minimum amount of money on fuel.

The Problem: A Traffic Jam of Electricity

Usually, these roads are always open. But sometimes, closing a specific road can actually make traffic flow better and cheaper. This is called Optimal Transmission Switching (OTS). It's like a GPS that says, "Hey, if we close Main Street, everyone will take the side streets, and the whole city will move faster."

However, figuring out exactly which roads to close is a nightmare for computers. The math gets incredibly complicated because the roads can be open or closed (on/off), and the electricity has to follow strict physical laws (like water flowing downhill).

To solve this, mathematicians use a simplified model called DC-OTS. But even this simplified model has a "bug." To make the math work when a road is closed, they use a giant, scary number called Big-M.

The Big-M Problem:
Think of Big-M as a "safety buffer." When a road is closed, the model says, "The voltage difference between these two neighborhoods could be anything up to this huge number."

• The Issue: Because the planners don't know exactly how big that number needs to be, they just pick a massive, arbitrary number (like 1,000,000) to be safe.
• The Consequence: This makes the computer's job incredibly hard. It's like trying to find a needle in a haystack when the haystack is the size of a mountain. The computer wastes time checking impossible scenarios because the safety buffer is too loose.

The Old Way: Guessing the Longest Path

Previously, people thought the only way to fix this was to solve a problem called the Longest Path Problem. Imagine trying to find the absolute longest possible route a car could take through the city without getting stuck. This is a famous "impossible" math problem (NP-hard) that takes forever to solve. So, people just gave up and used those loose, arbitrary Big-M numbers, making the computer slow and inefficient.

The New Solution: The "Smart Fence"

This paper introduces a clever new trick. Instead of trying to find the longest path (which is too hard), the authors looked at the shape of the problem itself. They treated the math like a geometric puzzle.

The Analogy of the Cycle (The Roundabout):
Imagine a group of roads forming a perfect circle (a cycle).

1. The Old View: If you close one road in the circle, the electricity has to go the "long way around" the other side.
2. The New Insight: The authors realized that you don't need to know the exact longest path. You just need to build a Smart Fence (a mathematical inequality) that hugs the possible solutions tightly.

They created a new type of rule called C-PVIs (Cycle-Induced Path-Based Valid Inequalities).

How it works in plain English:
Instead of saying, "The voltage difference could be up to 1,000,000," the new rule says:
"If Road A is closed, the electricity must take the path through Roads B, C, and D. The voltage difference cannot be larger than the sum of the 'resistance' of B, C, and D."

They proved that these new rules are Facet-Defining.

• Metaphor: Imagine the set of all possible solutions is a blob of clay. The "Big-M" method tries to wrap that clay in a giant, loose cardboard box. The new method carves a custom, tight-fitting suit of armor around the clay. It fits perfectly, leaving no empty space for the computer to waste time exploring.

Why This Matters

1. Speed: By tightening these "safety buffers" (the Big-M values) without solving the impossible "longest path" problem, the computer can solve the switching problem much, much faster.
2. Efficiency: It allows power grid operators to switch lines on and off more frequently and effectively, saving money and reducing waste.
3. No Magic Needed: They didn't need a supercomputer to find the longest path; they just needed a better geometric understanding of the problem.

Summary

The authors took a messy, slow computer problem about switching power lines and realized the "safety rules" were too loose. Instead of trying to calculate the impossible "worst-case scenario," they built a set of tight, custom-fit mathematical fences (C-PVIs) that describe the problem perfectly. This lets computers solve the puzzle quickly, saving money and keeping the lights on more efficiently.

Technical Summary

1. Problem Statement

The paper addresses the Direct-Current Optimal Transmission Switching (DC-OTS) problem. DC-OTS aims to minimize power generation costs by optimally reconfiguring the transmission network topology (switching lines on or off) using a linearized power flow model (DCOPF).

• Current Formulation: The problem is typically modeled as a Mixed-Integer Linear Program (MILP) using "big-M" formulations (specifically the angle-based model by Fisher et al.).
• The Core Challenge: The big-M parameters ($M_{ij}$) represent upper bounds on voltage angle differences across inactive lines.
  • If $M_{ij}$ is too small, the formulation excludes feasible solutions.
  • If $M_{ij}$ is too large (conservative/arbitrary), the Linear Programming (LP) relaxation becomes weak, leading to poor computational performance and slow convergence.
• Existing Limitations:
  • Tightening these bounds theoretically requires solving the Longest Path Problem (LPP) on the network, which is NP-hard.
  • Previous approaches either use loose fixed bounds (e.g., $2\pi$), which can exclude feasible solutions or are invalid for non-adjacent buses, or use flow-based cuts that implicitly tighten angle bounds without explicitly modeling angle variables.
  • There is a lack of polyhedral analysis for substructures that explicitly include angle variables.

2. Methodology

The authors propose a novel polyhedral analysis of an angle-based relaxation of the DC-OTS model to derive stronger constraints.

A. Relaxation Construction

The authors define a relaxation ($R^{\theta,y}_C$) over a cycle $C$ in the network graph.

1. Path-Based Bounds: They utilize the physical relationship where the voltage angle difference between two buses is bounded by the sum of line weights (reactance $\times$ capacity) along the path connecting them.
2. Disjunctive Structure: For any pair of buses $(m, n)$ in a cycle, there are two paths: a shorter path ($\rho_{mn}$) and a longer path ($\bar{\rho}_{mn}$). The angle difference bound depends on which path is active (all lines on the path are switched on).
3. Extended Formulation: They construct an extended formulation using auxiliary binary variables ($z_{mn}, \bar{z}_{mn}, \zeta_{mn}$) to indicate the status of the shorter and longer paths. This formulation explicitly captures the disjunctive logic:
   • If the shorter path is active, the bound is the weight of the shorter path.
   • If the shorter is inactive but the longer is active, the bound is the weight of the longer path.
   • If neither is fully active, the bound defaults to a global big-M.

B. Projection and Derivation

Using Fourier-Motzkin elimination, the authors project this extended formulation back into the original variable space $(\theta, y)$ (angle differences and line status variables).

• This projection yields a new class of inequalities called Cycle-Induced Path-Based Valid Inequalities (C-PVIs).
• The C-PVI (Equation 16) explicitly bounds the angle difference $|\delta\theta_{mn}|$ based on the status of lines in the shorter and longer paths.

C. Polyhedral Analysis

The authors prove the strength of these inequalities:

1. Convex Hull: They demonstrate that the extended formulation is locally ideal and sharp, meaning its projection exactly describes the convex hull of the relaxation.
2. Facet-Defining: They prove that the C-PVIs are facet-defining for the convex hull of the relaxation set. This means these inequalities are necessary to fully describe the feasible region and cannot be derived from other standard constraints.

3. Key Contributions

1. Novel Polyhedral Analysis: The paper is the first to analyze the polyhedral geometry of a DC-OTS substructure that explicitly includes angle variables, moving beyond previous flow-only analyses.
2. New Inequalities (C-PVIs): Derivation of Cycle-Induced Path-Based Valid Inequalities. Unlike previous cycle-based inequalities (CVIs) that bound power flows, C-PVIs directly tighten the bounds on voltage angle differences.
3. Theoretical Guarantees: Proof that C-PVIs are facet-defining, ensuring they provide the tightest possible linear relaxation for the specific substructure analyzed.
4. Computational Efficiency: The separation of these inequalities can be done in polynomial time by enumerating bus pairs within cycles and applying a screening test, avoiding the need to solve the NP-hard Longest Path Problem exactly.

4. Results and Significance

• Tighter Relaxations: By explicitly modeling the relationship between line switching and angle differences, C-PVIs provide significantly tighter bounds than traditional big-M formulations or flow-based cuts. This reduces the "integrality gap" in the MILP solver.
• Scalability: The method avoids the computational intractability of solving the LPP for every pair of buses. Instead, it leverages the cycle structure of the network to derive valid bounds efficiently.
• Bridging Theory and Practice: The work challenges the prevailing belief that tightening angle bounds requires solving the LPP. It shows that valid, tight bounds can be derived through polyhedral projection without solving the NP-hard problem.
• Future Impact: These inequalities can be integrated into branch-and-cut algorithms for DC-OTS, potentially leading to faster solution times and the ability to solve larger, more realistic power system instances to optimality.

Summary of the C-PVI Logic

For a cycle $C$ and a bus pair $(m,n)$ with a shorter path $\rho_{mn}$ and longer path $\bar{\rho}_{mn}$:
$$|\delta\theta_{mn}| \leq w(\rho_{mn}) + \left(|\rho_{mn}| - \sum_{(i,j)\in\rho_{mn}} y_{ij}\right)\Delta(\rho) + \left(|\bar{\rho}_{mn}| - \sum_{(i,j)\in\bar{\rho}_{mn}} y_{ij}\right)\Delta(M)$$
Where:

• $w(\cdot)$ is the path weight.
• $y_{ij}$ are binary line status variables.
• $\Delta(\rho)$ and $\Delta(M)$ are coefficients derived from the difference in path weights and the big-M parameter.

This inequality dynamically adjusts the angle bound: if lines on the shorter path are active ($y=1$), the bound tightens to $w(\rho_{mn})$; if lines are inactive, the bound relaxes appropriately but remains tighter than a generic big-M.