Convex Relaxations of the Network Flow Problem under Cycle Constraints

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Article number8709783
Pages (from-to)64-73
Number of pages10
JournalIEEE Transactions on Control of Network Systems
Volume7
Issue number1
DOIs
StatePublished - Mar 2020

Keywords

  • Energy management
  • network theory (graphs)
  • optimization methods
  • power generation dispatch

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Signal Processing
  • Computer Networks and Communications
  • Control and Optimization

Fingerprint Dive into the research topics of 'Convex Relaxations of the Network Flow Problem under Cycle Constraints'. Together they form a unique fingerprint.

Cite this