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 -