AC-Feasibility on Tree Networks is NP-Hard

Karsten Lehmann; Alban Grastien; Pascal Van Hentenryck

doi:10.1109/TPWRS.2015.2407363

AC-Feasibility on Tree Networks is NP-Hard

Karsten Lehmann, Alban Grastien, Pascal Van Hentenryck

Research output: Contribution to journal › Article › peer-review

151 Citations (Scopus)

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.

Original language	English
Article number	7063278
Pages (from-to)	798-801
Number of pages	4
Journal	IEEE Transactions on Power Systems
Volume	31
Issue number	1
DOIs	https://doi.org/10.1109/TPWRS.2015.2407363
Publication status	Published - Jan 2016
Externally published	Yes

Access to Document

10.1109/TPWRS.2015.2407363

Cite this

@article{9e60d082cb2b488295ef18b9862cdba1,

title = "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.",

keywords = "Computational complexity, optimal power flow (OPF)",

author = "Karsten Lehmann and Alban Grastien and {Van Hentenryck}, Pascal",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.",

year = "2016",

month = jan,

doi = "10.1109/TPWRS.2015.2407363",

language = "English",

volume = "31",

pages = "798--801",

journal = "IEEE Transactions on Power Systems",

issn = "0885-8950",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "1",

}

TY - JOUR

T1 - AC-Feasibility on Tree Networks is NP-Hard

AU - Lehmann, Karsten

AU - Grastien, Alban

AU - Van Hentenryck, Pascal

PY - 2016/1

Y1 - 2016/1

N2 - 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.

AB - 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.

KW - Computational complexity

KW - optimal power flow (OPF)

UR - http://www.scopus.com/inward/record.url?scp=84925070737&partnerID=8YFLogxK

U2 - 10.1109/TPWRS.2015.2407363

DO - 10.1109/TPWRS.2015.2407363

M3 - Article

SN - 0885-8950

VL - 31

SP - 798

EP - 801

JO - IEEE Transactions on Power Systems

JF - IEEE Transactions on Power Systems

IS - 1

M1 - 7063278

ER -

AC-Feasibility on Tree Networks is NP-Hard

Abstract

Access to Document

Other files and links

Fingerprint

Cite this