Strong NP-hardness of AC power flows feasibility

DOI10.1016/J.ORL.2019.08.009MaRDI QIDQ2294366zbMATH OpenOpenAlexFDO

Authors Abhinav Verma, Daniel Bienstock

Publication date 10 February 2020

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.07315

zbMATH Keywords

approximation algorithmsNP-completenesspower flows

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Abstract: We present a rigorous proof of strong NP-hardness of the AC-OPF problem.

Recommendations

• Modelling the power supply network -- hardness and approximation
• A linear-programming approximation of AC power flows
• Probabilistically Robust AC Optimal Power Flow
• Strong SOCP relaxations for the optimal power flow problem
• Convex Restriction of Power Flow Feasibility Sets
• Designing AC power grids using integer linear programming
• Combinatorial Optimization of AC Optimal Power Flow With Discrete Demands in Radial Networks
• AC optimal power flow: a conic programming relaxation and an iterative MILP scheme for global optimization
• Asymptotically tight conic approximations for chance-constrained AC optimal power flow

Cites work

• A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables
• Electrical transmission system cascades and vulnerability. An operations research viewpoint
• Fast Multiple-Precision Evaluation of Elementary Functions
• Graph minors. II. Algorithmic aspects of tree-width
• LP formulations for polynomial optimization problems
• Lagrangian duality and branch-and-bound algorithms for optimal power flow
• Matrix minor reformulation and SOCP-based spatial branch-and-cut method for the AC optimal power flow problem
• Network flows. Theory, algorithms, and applications.
• Optimization Strategies for the Vulnerability Analysis of the Electric Power Grid

Cited in

(10)

• Operations research in optimal power flow: a guide to recent and emerging methodologies and applications
• A survey on conic relaxations of optimal power flow problem
• A bilevel approach for identifying the worst contingencies for nonconvex alternating current power systems
• Two-Stage Robust Quadratic Optimization with Equalities and Its Application to Optimal Power Flow
• Graphical models for optimal power flow
• Survey of optimization models for power system operation and expansion planning with demand response
• Mathematical programming formulations for the alternating current optimal power flow problem
• Mathematical programming formulations for the alternating current optimal power flow problem
• A generalised approach for efficient computation of look ahead security constrained optimal power flow
• Algorithmic mechanism design with investment

This page was built for publication: Strong NP-hardness of AC power flows feasibility

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294366)