Abstract
The AC-Feasibility (AC-FEAS) problem is a cornerstone of power systems engineering, determining if a set of power demands can be met within physical and operational constraints. While tree-structured networks are often considered computationally simpler than meshed grids, this paper proves that AC-FEAS remains NP-Hard even on radial topologies. Through a polynomial-time reduction from the Subset Sum problem to a star-shaped network, the authors demonstrate that the non-convexity of AC power flow equations can lead to disconnected feasible regions, posing a fundamental challenge to global optimization.
Introduction
In power systems, the AC-Feasibility problem asks whether a valid dispatch exists for a given set of loads and generators such that Ohm’s and Kirchhoff’s laws are satisfied alongside voltage and line capacity limits. Historically, researchers observed that convex relaxations, such as Second-Order Cone Programming (SOCP), often yield exact solutions for tree-structured (radial) networks. This led to the hypothesis that AC-FEAS might be solvable in polynomial time for trees.
However, this paper settles the debate by proving the problem is NP-Hard. The complexity arises not from the network topology itself, but from the inherent nonlinearities of the AC power flow equations. These nonlinearities can create "disconnected" feasible regions, where valid operating points are separated by infeasible space, preventing local search methods from guaranteeing a solution.
Methodology
The authors establish NP-Hardness using a polynomial-time reduction from the Subset Sum problem, a classic NP-complete problem where one must determine if a subset of integers $M$ sums exactly to a target value $w$.
The Reduction Construction
The proof utilizes a "star" network—the simplest form of a tree—where a central load bus is connected to multiple generator buses. Each integer in the Subset Sum set $M$ is mapped to a specific generator, and the target sum $w$ is mapped to the central load demand.
The Mathematical "Lock"
The core of the reduction lies in the relationship between real power ($p$) and reactive power ($q$). The authors prove that for specific line configurations, the ratio $p/q$ is a strictly monotonic function of the phase angle difference. By carefully selecting line parameters—specifically conductance ($g$) and susceptance ($b$)—they create a physical "lock." This forces each generator into a binary state: it must either be "OFF" (zero phase angle difference) or "ON" at a precise setpoint (phase angle difference $\Delta$). This binary behavior directly encodes the "include or exclude" logic of the Subset Sum problem into the physics of the power grid.
Key Insights
- Monotonicity of Power Ratios: The insight that the ratio of real to reactive power flow can encode logic is pivotal. It allows the physical constraints of the wires to act as logic gates.
- Fragmented Feasibility: The hardness is a direct consequence of disconnected feasible regions. In such landscapes, a solution might exist in one "island" of feasibility while a solver is stuck in another, with no continuous path between them.
- Minimal Hardness Requirements: The proof is robust, holding even under simplified conditions:
- Fixed voltage magnitudes (1.0 p.u.).
- Standard, realistic line parameters (positive $g$, negative $b$).
- Minimal tree topology (star network).
Results and Implications
The formal proof that AC-Feasibility on trees is NP-Hard has significant implications for the field of power system optimization. It explains why convex relaxations require specific, often stringent, conditions to be "tight." If relaxations were universally tight on trees, it would imply P=NP.
Furthermore, the study demonstrates that imposing bounds on phase angle differences—often used as a proxy for thermal limits—is sufficient to trigger this computational hardness. This suggests that even "well-behaved" operational constraints can introduce significant complexity.
Conclusion and Future Work
While this work provides a definitive complexity result, it leaves open questions regarding the "phase transition" of hardness. The proof assumes fixed voltage magnitudes and exact load satisfaction. Previous research has shown that if "load over-satisfaction" is permitted (allowing generators to produce more than the required demand), the problem can become convex and thus "easy."
Future research may focus on identifying the exact boundaries where physical constraints transition from a convex, easily solvable set to a fragmented, NP-Hard landscape. Additionally, exploring how narrow voltage bands (e.g., ±5%) affect this hardness in practical distribution systems remains an important area for empirical and theoretical study.
Summary updated