Source-linked AI summary
AC-Feasibility on Tree Networks is NP-Hard
Karsten Lehmann, Alban Grastien, Pascal Van Hentenryck
TL;DR
Power-system optimization includes AC-feasibility, the question of whether generator dispatch can meet demand, amid interest in relaxations that can be tight on trees. This paper proves AC-feasibility is NP-hard on tree networks using a construction centered on star networks and one load, under specified voltage, generation, capacity, or angle-bound conditions. The result indicates that convex relaxations cannot be tight on tree networks without additional conditions.
Problem
AC-feasibility asks whether some generator dispatch can satisfy a given demand, a subproblem in nonlinear, nonconvex power-flow applications.
Method
The paper proves hardness through an AC-feasibility construction for a star network with one load, using fixed unit voltage magnitudes and bounded phase-angle differences.
Results
AC-feasibility on tree networks is NP-hard.
Takeaways & Limitations
The result indicates that convex relaxations cannot be tight on tree networks without additional conditions on the network.
Abstract
from arXiv · showhide
Recent years have witnessed significant interest in convex relaxations of the power flows, several papers showing that the second-order cone relaxation is tight for tree networks under various conditions on loads or voltages. This paper shows that AC-feasibility, i.e., to find whether some generator dispatch can satisfy a given demand, is NP-Hard for tree networks.
NOMENCLATURE
The nomenclature defines the network, its buses, lines, electrical parameters, phase-angle quantities, and real and reactive power quantities.
- N denotes the AC network, with N, N_G, and N_L representing buses, generators, and loads, respectively.
- E is the set of lines, while E_d is the set of directed lines.
- b and g denote line susceptance and conductance, while s denotes line capacity.
- Δ is the maximum phase-angle difference and Θ denotes phase angle or angles.
- p and q denote real and reactive line power flows, while P and Q denote real and reactive power demands.
I. INTRODUCTION
AC-feasibility is a subproblem in nonlinear, nonconvex power-system optimization: determine whether generator dispatch can satisfy fixed demand. Against prior hardness and relaxation results, the paper proves NP-hardness even on tree networks.
- AC-feasibility asks whether some generator dispatch can satisfy a given demand.It appears as a subproblem in applications such as optimal power flow.
- Optimal power-flow applications optimize objectives over steady-state power-flow equations that are nonlinear and nonconvex.
- The first NP-hardness proof for AC-feasibility used a cyclic network and a variant of the DC model with a sine term.That construction fixed voltage magnitudes at 1, set conductances to 0, and ignored reactive power.
- Prior work showed second-order cone relaxations can be tight on tree networks under conditions involving loads or voltage bounds.Tree networks are important because they are backbones of distribution systems.
- The paper proves AC-feasibility is NP-hard for tree networks without generation bounds and with realistic conductances, susceptances, and phase-angle bounds.
II. PROBLEM DEFINITION
The problem fixes real and reactive demands, uses unit voltage magnitudes and bounded phase differences, and seeks phase angles and line flows satisfying AC power-flow constraints. The formulation also imposes sign and relationship conditions on electrical parameters and connects angle bounds to line capacities.
- The input contains fixed real-power demands P and reactive-power demands Q, with all voltage magnitudes fixed to one.
- Lines have a maximum phase-angle difference satisfying 0 < Δ ≤ π/2.
- The assumptions require susceptance b ≤ 0 and conductance g ≥ 0, together with a condition relating b, g, and Δ.
- Every bus is either a load or a generator, and E and E_d represent undirected and directed lines, respectively.A bus may have zero demand.
- Feasibility requires finding phase angles and real and reactive line flows satisfying the AC power-flow equations.The line-flow laws express p_ij and q_ij using conductance, susceptance, and phase-angle differences.
- Bounding phase-angle differences is equivalent to enforcing a line capacity or thermal limit.The paper uses angle bounds because they simplify the proof.
III. AC-FEASIBILITY ON STAR NETWORKS IS NP-HARD
The paper proves NP-hardness of AC-feasibility for star networks by reducing subset sum to a constructed AC network and showing feasibility in both directions. The proof uses phase-angle properties and power-conservation constraints to establish the correspondence.
- AC-feasibility is NP-hard even for star networks with one load.The section identifies disconnected feasibility regions in a prior 2-bus example as inspiration for the proof.
- Phase-angle lemmas establish that feasible generator angles have the required sign and that the real-to-reactive power ratio is unique for each phase-angle difference.These properties constrain feasible solutions sufficiently to recover the encoded subset.
- The reduction starts from subset sum and constructs a star AC network whose generator choices encode a candidate subset.The construction uses a set M, target w, one load, and generator leaves connected to it.
- If the subset-sum instance is solvable, assigning zero angles to excluded elements and bounded positive differences to selected elements yields a feasible AC solution.The construction satisfies phase-angle constraints, AC power laws, conservation, and generation constraints.
- Conversely, any feasible AC solution defines a selected subset through positive generator-load angle differences, and conservation forces its encoded values to sum to the target.The proof uses non-positive summands and the phase-angle lemmas to show selected branches attain the required contribution.
IV. CONCLUSION
The paper concludes that AC-feasibility on tree networks is NP-hard, so convex relaxations cannot be tight on tree networks without additional network conditions. The proof relies on fixed voltage magnitudes and at least one of several operational bounds.
- AC-feasibility on tree networks is NP-hard, limiting unconditional tightness claims for convex relaxations.The conclusion states that additional conditions on the network are necessary for convex relaxations to be tight.
- The proof fixes voltage magnitudes to 1 and relies on arbitrarily small voltage bounds plus generation, capacity, or phase-angle-difference constraints.These assumptions define the scope of the demonstrated hardness result.