TY - GEN
T1 - The maximum transmission switching flow problem
AU - Grastien, Alban
AU - Rutter, Ignaz
AU - Wagner, Dorothea
AU - Wegner, Franziska
AU - Wolf, Matthias
N1 - Publisher Copyright:
© 2018 Association for Computing Machinery.
PY - 2018/6/12
Y1 - 2018/6/12
N2 - The Maximum Transmission Switching Flow (MTSF) is the problem of maximizing the power flow of a power grid by switching off lines. This static transmission design problem is known to be NP-hard even on strongly restricted graph classes. In this paper, we study the combinatorial structure of the MTSF problem and its relationship to familiar problems. We tackle the problem by exploiting the structure of the power grid leading to the first algorithms for MTSF having provable performance guarantees. We decrease the theoretical gap not only by developing algorithms with guarantees, but also by proving that the decision problem of MTSF is NP-hard even when the network contains only one generator and one load. In this context, we introduce the Dominating Theta Path, which is an exact algorithm on certain graph structures and can be used as a switching metric in general. Our simulations show that the algorithms provide very good results (in many cases near-optimal) on the NESTA benchmark cases that provide realistic thermal line limits.
AB - The Maximum Transmission Switching Flow (MTSF) is the problem of maximizing the power flow of a power grid by switching off lines. This static transmission design problem is known to be NP-hard even on strongly restricted graph classes. In this paper, we study the combinatorial structure of the MTSF problem and its relationship to familiar problems. We tackle the problem by exploiting the structure of the power grid leading to the first algorithms for MTSF having provable performance guarantees. We decrease the theoretical gap not only by developing algorithms with guarantees, but also by proving that the decision problem of MTSF is NP-hard even when the network contains only one generator and one load. In this context, we introduce the Dominating Theta Path, which is an exact algorithm on certain graph structures and can be used as a switching metric in general. Our simulations show that the algorithms provide very good results (in many cases near-optimal) on the NESTA benchmark cases that provide realistic thermal line limits.
KW - Approximation
KW - Graph algorithms
KW - Topology optimization
KW - Transmission network control
KW - Transmission switching
UR - http://www.scopus.com/inward/record.url?scp=85050181717&partnerID=8YFLogxK
U2 - 10.1145/3208903.3208910
DO - 10.1145/3208903.3208910
M3 - Conference contribution
T3 - e-Energy 2018 - Proceedings of the 9th ACM International Conference on Future Energy Systems
SP - 340
EP - 360
BT - e-Energy 2018 - Proceedings of the 9th ACM International Conference on Future Energy Systems
PB - Association for Computing Machinery, Inc
T2 - 9th ACM International Conference on Future Energy Systems, e-Energy 2018
Y2 - 12 June 2018 through 15 June 2018
ER -