TY - JOUR
T1 - Convex Relaxations of the Network Flow Problem under Cycle Constraints
AU - Zholbaryssov, Madi
AU - Domínguez-García, Alejandro D.
N1 - Funding Information:
Manuscript received August 21, 2018; revised February 22, 2019 and February 24, 2019; accepted April 16, 2019. Date of publication May 8, 2019; date of current version March 18, 2020. This work was supported in part by the U.S. Department of Energy (DOE) within the GEARED Initiative under Grant DE-0006341, in part by the Advanced Research Projects Agency-Energy (ARPA-E) within the NODES program under Award DEAR0000695, and in part by the DOE within the Consortium for Electric Reliability Technology Solutions program. Recommended by Associate Editor G. Como. (Corresponding author: Madi Zholbaryssov.) The authors are with the ECE Department, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA (e-mail:, zholbar1@ ILLINOIS.EDU; aledan@ILLINOIS.EDU). Digital Object Identifier 10.1109/TCNS.2019.2915390
PY - 2020/3
Y1 - 2020/3
N2 - In this paper, we consider the problem of optimizing the flows in a lossless flow network with additional nonconvex cycle constraints on nodal variables; such constraints appear in several applications, including electric power, water distribution, and natural gas networks. This problem is a nonconvex version of the minimum-cost network flow problem (NFP), and to solve it, we propose three different approaches. One approach is based on solving a convex approximation of the problem, obtained by augmenting the cost function with an entropy-like term to relax the nonconvex constraints. We show that the approximation error, for which we give an upper bound, can be made small enough for practical use. An alternative approach is to solve the classical NFP, that is, without the cycle constraints, and solve a separate optimization problem afterwards in order to recover the actual flows satisfying the cycle constraints; the solution of this separate problem maximizes the individual entropies of the cycles. The third approach is based on replacing the nonconvex constraint set with a convex inner approximation, which yields a suboptimal solution for the cyclic networks with each edge belonging to at most two cycles. We validate the practical usefulness of the theoretical results through numerical examples, in which we study the standard test systems for water and electric power distribution networks.
AB - In this paper, we consider the problem of optimizing the flows in a lossless flow network with additional nonconvex cycle constraints on nodal variables; such constraints appear in several applications, including electric power, water distribution, and natural gas networks. This problem is a nonconvex version of the minimum-cost network flow problem (NFP), and to solve it, we propose three different approaches. One approach is based on solving a convex approximation of the problem, obtained by augmenting the cost function with an entropy-like term to relax the nonconvex constraints. We show that the approximation error, for which we give an upper bound, can be made small enough for practical use. An alternative approach is to solve the classical NFP, that is, without the cycle constraints, and solve a separate optimization problem afterwards in order to recover the actual flows satisfying the cycle constraints; the solution of this separate problem maximizes the individual entropies of the cycles. The third approach is based on replacing the nonconvex constraint set with a convex inner approximation, which yields a suboptimal solution for the cyclic networks with each edge belonging to at most two cycles. We validate the practical usefulness of the theoretical results through numerical examples, in which we study the standard test systems for water and electric power distribution networks.
KW - Energy management
KW - network theory (graphs)
KW - optimization methods
KW - power generation dispatch
UR - http://www.scopus.com/inward/record.url?scp=85082298865&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85082298865&partnerID=8YFLogxK
U2 - 10.1109/TCNS.2019.2915390
DO - 10.1109/TCNS.2019.2915390
M3 - Article
AN - SCOPUS:85082298865
VL - 7
SP - 64
EP - 73
JO - IEEE Transactions on Control of Network Systems
JF - IEEE Transactions on Control of Network Systems
SN - 2325-5870
IS - 1
M1 - 8709783
ER -