Source-linked AI summary
Strong NP-hardness of AC power flows feasibility
Daniel Bienstock, Abhinav Verma
TL;DR
The paper addresses the fundamental complexity of AC-OPF feasibility, where prior evidence included only weak NP-hardness on trees. It develops a rigorous reduction-based proof and establishes strong NP-hardness on general graphs.
Problem
The paper examines the fundamental computational complexity of nonlinear, nonconvex AC-OPF, extending limited prior evidence of weak NP-hardness on trees.
Method
The proof reduces one-in-three 3-SAT to AC power-flow feasibility while accounting for potentially irrational solution coordinates.
Results
Testing feasibility of the nonlinear, nonconvex system is strongly NP-hard, even when input bit lengths are polynomially bounded in the number of buses.
Takeaways & Limitations
The result establishes strong NP-hardness of AC-OPF feasibility on general graphs.
Takeaways & Limitations
NP membership is not established because feasible solutions may contain irrational flow or angle values.
Abstract
from arXiv · showhide
We present a rigorous proof of strong NP-hardness of the AC-OPF problem.
1 Introduction
The section introduces AC-OPF as a nonlinear, nonconvex feasibility problem and establishes strong NP-hardness on general graphs. The proof addresses the challenge that feasible solutions may contain irrational coordinates.
- Background: AC-OPF is a nonlinear, nonconvex problem arising in electrical-network analysis.On bounded-tree-width graphs, it can be solved to any given tolerance.
- Contribution: The note presents a rigorous proof that AC-OPF is strongly NP-hard on general graphs.The proof builds on a section of a PhD thesis.
- Proof challenge: Irrational coordinates in AC-OPF solutions require an elaboration of the proof technique.A related weak-NP-hardness reduction is noted as encoding some irrational quantities.
- Model: The model uses a directed transmission graph with line reactances, phase-angle-difference limits, bus net-generation values, and flow and phase-angle variables.It assumes zero line resistances and unconstrained reactive power flows and injections.
- Complexity result: Feasibility of the nonlinear, nonconvex lossless AC power-flow system remains NP-hard when input bit-length is polynomially bounded in the number of buses.This is the meaning of strong NP-hardness stated in the section.
4. Applying a similar reasoning to line (2, 4) we get · 5. The flow conservation equations at buses 1 and 2 are, respectively,
The construction shows that each component operates in one of two phase-angle modes, producing sharply separated throughput ranges. These modes are then assembled into variable and clause networks to establish strong NP-hardness, while membership in NP remains unresolved because feasible solutions may require irrational values.
- 5. The flow conservation equations at buses 1 and 2 are, respectively,: The flow analysis identifies two operating modes, with θ close to zero or close to θ0.These are designated Mode I and Mode II.
- 5. The flow conservation equations at buses 1 and 2 are, respectively,: Mode I has throughput less than 0.1592, while θ = 0.1057 and δ = 0 yields a feasible throughput greater than 0.1579.
- 5. The flow conservation equations at buses 1 and 2 are, respectively,: Mode II has throughput at least 0.77464 and less than 0.88671, while θ = 0.6952 and δ = 0 yields a feasible throughput greater than 0.88648.
- 1.2 NP-hardness construction: The THROUGHPUT decision problem asks whether a lossless AC transmission system with one generator and one load can transmit at least T units of power.
- 1.2 NP-hardness construction: The reduction from one-in-three 3-SAT builds variable networks from paired B copies and clause networks from three B copies.Variable networks also include buses sj, ¯sj, and tj; clause networks correspond to clauses Ci = (p ∨q ∨r).
- 1.2 NP-hardness construction: A demand of at least n(S+H) + m(2S+H) at node D implies that the one-in-three 3SAT instance is satisfiable.The proof forces one mode assignment per variable pair and exactly one Mode II network among each clause’s three literal copies.
- 1.2 NP-hardness construction: If the one-in-three 3SAT instance is satisfiable, the constructed network has a feasible solution consuming at least n(S + H) + m(2S + H) demand at D.The feasible assignment operates Bj in Mode II iff xj = true and matches literal-copy modes accordingly.
- 1.3 Membership in NP: NP membership is not established because feasible solutions may contain irrational fij and possibly irrational θi values.The paper conjectures that an approximate system with | sin(θi −θj) −xijfij| ≤ϵ belongs to NP.