Physics of power networks makes hard optimization problems easy to solve
The DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
Abstract
We have recently observed and justified that the optimal power flow (OPF) problem with a quadratic cost function may be solved in polynomial time for a large class of power networks, including IEEE benchmark systems. In this work, our previous result is extended to OPF with arbitrary convex cost functions and then a more rigorous theoretical foundation is provided accordingly. First, a necessary and sufficient condition is derived to guarantee the solvability of OPF in polynomial time through its Lagrangian dual. Since solving the dual of OPF is expensive for a large-scale network, a far more scalable algorithm is designed by utilizing the sparsity in the graph of a power network. The computational complexity of this algorithm is related to the number of cycles of the network. Furthermore, it is proved that due to the physics of a power network, the polynomial-time algorithm proposed here always solves every full AC OPF problem precisely or after two mild modifications.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Zero Duality Gap in Optimal Power Flow Problem
Lavaei, J., & Low, S. H. (2012) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2011.2160974 · Cited by 1,195 · cited 10×
“As stated in [8], [17], [14], modification (i) often has a negligible effect (see Chapter 15 of [17] for more details).”
BackgroundMethodSelf-citationMomoh, J. A., Adapa, R., & El-Hawary, M. E. (1999) · IEEE Transactions on Power Systems · doi:10.1109/59.744492 · Cited by 836 · cited 2×
“, power loss or generation cost) subject to network and physical constraints [1], [2].”
BackgroundRadial Distribution Load Flow Using Conic Programming
Jabr, R. A. (2006) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2006.879234 · Cited by 713 · cited 3×
“In order to solve OPF more efficiently, different conic and convex relaxations have been proposed in the past decade [11], [12], [13].”
BackgroundMomoh, J. A., El-Hawary, M. E., & Adapa, R. (1999) · IEEE Transactions on Power Systems · doi:10.1109/59.744495 · Cited by 645 · cited 2×
“, power loss or generation cost) subject to network and physical constraints [1], [2].”
BackgroundA survey of the optimal power flow literature
Huneault, M., & Galiana, F. D. (1991) · IEEE Transactions on Power Systems · doi:10.1109/59.76723 · Cited by 603
Semidefinite programming for optimal power flow problems
Bai, X., Wei, H., Fujisawa, K., & Wang, Y. (2008) · International Journal of Electrical Power & Energy Systems · doi:10.1016/j.ijepes.2007.12.003 · Cited by 573 · cited 1×
“In order to solve OPF more efficiently, different conic and convex relaxations have been proposed in the past decade [11], [12], [13].”
BackgroundAn interior point nonlinear programming for optimal power flow problems with a novel data structure
Wei, H., Sasaki, H., Kubokawa, J., & Yokoyama, R. (1998) · IEEE Transactions on Power Systems · doi:10.1109/59.708745 · Cited by 383
On Computational Issues of Market-Based Optimal Power Flow
Wang, H., Murillo-Sanchez, C. E., Zimmerman, R. D., & Thomas, R. J. (2007) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2007.901301 · Cited by 352 · cited 1×
“Several algorithms have been proposed for solving this highly nonconvex problem, including linear programming, quadratic programming, nonlinear programming, Lagrange relaxation, interior point methods, artificial intelligence, artificial neural network, fuzzy logic, genetic algorithm, evolutionary programming and part…”
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 · cited 1×
“A similar result is also derived in [32] using a different formulation for the OPF problem.”
Result
Cited by
Branch Flow Model: Relaxations and Convexification—Part I
Farivar, M., & Low, S. H. (2013) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2013.2255317 · Cited by 1,541
“I. INTRODUCTION”
A Survey of Distributed Optimization and Control Algorithms for Electric Power Systems
Molzahn, D. K., Dorfler, F., Sandberg, H., Low, S. H., Chakrabarti, S., Baldick, R., & Lavaei, J. (2017) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2017.2720471 · Cited by 1,273
Self-citationConvex Relaxation of Optimal Power Flow—Part II: Exactness
Low, S. H. (2014) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2014.2323634 · Cited by 523
Exact Convex Relaxation of Optimal Power Flow in Radial Networks
Gan, L., Li, N., Topcu, U., & Low, S. H. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2332712 · Cited by 500
Real-Time Energy Management in Microgrids
Shi, W., Li, N., Chu, C.-C., & Gadh, R. (2017) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2015.2462294 · Cited by 357
The QC Relaxation: A Theoretical and Computational Study on Optimal Power Flow
Coffrin, C., Hijazi, H. L., & Van Hentenryck, P. (2016) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2015.2463111 · Cited by 341
Strong SOCP Relaxations for the Optimal Power Flow Problem
Kocuk, B., Dey, S. S., & Sun, X. A. (2016) · Operations Research · doi:10.1287/opre.2016.1489 · Cited by 281
Dynamic Network Energy Management via Proximal Message Passing
Kraning, M. (2014) · now publishers, Inc. eBooks · doi:10.1561/9781601987150 · Cited by 247
Dynamic Network Energy Management via Proximal Message Passing
Kraning, M., Chu, E., Lavaei, J., & Boyd, S. (2014) · Foundations and Trends in Optimization · doi:10.1561/2400000002 · Cited by 237
Self-citationQuadratically constrained quadratic programs on acyclic graphs with application to power flow
Bose, S., Gayme, D. F., Chandy, K. M., & Low, S. H. (2012) · arXiv · doi:10.48550/arxiv.1203.5599 · Cited by 131
Optimal power flow in distribution networks
(2018) · Metaheuristic Optimization in Power Engineering · doi:10.1049/pbpo131e_ch9 · Cited by 15
Exact Convex Relaxation of Optimal Power Flow in Tree Networks
Gan, L., Li, N., Topcu, U., & Low, S. H. (2012) · arXiv · doi:10.48550/arxiv.1208.4076 · Cited by 11
Metadata
- Authors
- Sojoudi, S., & Lavaei, J.
- Venue
- 2012 IEEE Power and Energy Society General Meeting
- Publisher
- IEEE
- Published
- 2012-07
- Pages
- 1-8
- OpenAlex
- W2122700623
- Cited by
- 164
- References
- 20
- FWCI
- 28.66
- Type
- conference paper
- Language
- en
- Open access
- closed
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.