TY - GEN
T1 - A mixed integer program for the spanning distribution forest of a power network
AU - Palk, Michael
AU - Jovanovic, Raka
AU - Vob, Stefan
N1 - Publisher Copyright:
© 2019 IEEE.
PY - 2019/1/31
Y1 - 2019/1/31
N2 - In this paper we focus on solving the graph problem of the spanning distribution forest of a power network (SDFPN). The interest for the SDFPN comes from the fact that it well represents practical problems related to the partitioning of power distribution systems. It is closely related to the problem of maximal partitioning of supply demand graphs (MPGSD) and the capacitated spanning forest (CSF) problem that are used for modeling similar real-world systems. It has an advantage, compared to these problems, that it incorporates constraints related to ampacity, radiality, and the balance of consumption/generation in a partition. In this work, a mixed integer program (MIP) is developed for finding optimal solutions for the SDFPN. Next, a greedy constructive algorithm is designed for finding feasible solutions for large problem instances at low computational costs. In the computational experiments, we evaluate the size of graphs that can be solved to optimality using the MIP. The solutions acquired in this way are used to assess the performance of the proposed greedy algorithm.
AB - In this paper we focus on solving the graph problem of the spanning distribution forest of a power network (SDFPN). The interest for the SDFPN comes from the fact that it well represents practical problems related to the partitioning of power distribution systems. It is closely related to the problem of maximal partitioning of supply demand graphs (MPGSD) and the capacitated spanning forest (CSF) problem that are used for modeling similar real-world systems. It has an advantage, compared to these problems, that it incorporates constraints related to ampacity, radiality, and the balance of consumption/generation in a partition. In this work, a mixed integer program (MIP) is developed for finding optimal solutions for the SDFPN. Next, a greedy constructive algorithm is designed for finding feasible solutions for large problem instances at low computational costs. In the computational experiments, we evaluate the size of graphs that can be solved to optimality using the MIP. The solutions acquired in this way are used to assess the performance of the proposed greedy algorithm.
KW - Graph partitioning
KW - Greedy algorithm
KW - Mixed integer programming
KW - Power network
KW - Spanning distribution forest
UR - http://www.scopus.com/inward/record.url?scp=85062839993&partnerID=8YFLogxK
U2 - 10.1109/AIAIM.2019.8632783
DO - 10.1109/AIAIM.2019.8632783
M3 - Conference contribution
AN - SCOPUS:85062839993
T3 - 2019 China-Qatar International Workshop on Artificial Intelligence and Applications to Intelligent Manufacturing, AIAIM 2019
SP - 48
EP - 55
BT - 2019 China-Qatar International Workshop on Artificial Intelligence and Applications to Intelligent Manufacturing, AIAIM 2019
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2019 China-Qatar International Workshop on Artificial Intelligence and Applications to Intelligent Manufacturing, AIAIM 2019
Y2 - 1 January 2019 through 4 January 2019
ER -