AC-feasibility on tree networks is NP-hard
Abstract
Recent years have witnessed significant interest in convex relaxations of the power flows, with 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.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The exact AC power flow formulation would make the problem nonconvex and NP-hard, and mixed-integer applications proved untractable with present MINLP solvers.
“The use of the exact ('AC') power flow formulation would make the problem nonconvex and NPhard [22], and mixed-integer applications proved untractable with present MINLP solvers [35].”
From Congestion mitigation in unbalanced residential networks with OPF-based demand management (2022) · cites this paper as [22]
The use of the 'AC' power flow formulation is NP-hard.
“and the use of the 'AC' power flow formulation is NP-hard [22].”
From Congestion mitigation in unbalanced residential networks with OPF-based demand management (2022) · cites this paper as [22]
Cites
Inverter VAR control for distribution systems with renewables
Farivar, M., Clarke, C. R., Low, S. H., & Chandy, K. M. (2011) · 2011 IEEE International Conference on Smart Grid Communications (SmartGridComm) · doi:10.1109/smartgridcomm.2011.6102366 · Cited by 331 · see citing works
Geometry of injection regions of power networks
Zhang, B., & Tse, D. (2013) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2012.2208205 · Cited by 118 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Congestion mitigation in unbalanced residential networks with OPF-based demand management
Vanin, M., Van Acker, T., Ergun, H., D’hulst, R., Vanthournout, K., & Van Hertem, D. (2022) · Sustainable Energy, Grids and Networks · doi:10.1016/j.segan.2022.100936 · Cited by 7 · see citing works
- Authors
- Lehmann, K., Grastien, A., & Van Hentenryck, P.
- Affiliations
- Australian National University (AU)
- Venue
- IEEE Transactions on Power Systems
- Published
- 2016-01
- Volume
- 31
- Issue
- 1
- Pages
- 798-801
- ISSN
- 0885-8950 (ISSN-L)
- 1558-0679
- OpenAlex
- W2030641329
- Cited by
- 221
- References
- 2
- Citations by year
- 2026: 8 · 2025: 20 · 2024: 19 · 2023: 26 · 2022: 15 · 2021: 25 · 2020: 12 · 2019: 25 · 2018: 31 · 2017: 17 · 2016: 15 · 2015: 7 · 2014: 1
- FWCI
- 11.23
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Power Systems (publishedVersion)
- Topics
- Physical Sciences › Engineering › Electrical and Electronic Engineering › Optimal Power Flow Distribution
- Physical Sciences › Engineering › Electrical and Electronic Engineering › Electric Power System Optimization
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Keywords
- tree networks, NP-hardness, convex relaxation, second-order cone relaxation, power flow, generator dispatch, power system constraints, computational complexity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
