Convexification of generalized network flow problem

Somayeh Sojoudi, Salar Fattahi and Javad Lavaei, Convexification of Generalized Network Flow Problem, to appear in Mathematical Programming, pp. 1-39, 2017.

Abstract: This paper is concerned with the minimum-cost flow problem over an arbitrary flow network. In this problem, each node is associated with some possibly unknown injection and each line has two unknown flows at its ends that are related to each other via a nonlinear function. Moreover, all injections and flows must satisfy certain box constraints. This problem, named generalized network flow (GNF), is highly non-convex due to its nonlinear equality constraints. Under the assumption of monotonicity and convexity of the flow and cost functions, a convex relaxation is proposed, which is shown to always obtain globally optimal injections. This relaxation may fail to find optimal flows because the mapping from injections to flows is not unique in general. We show that the proposed relaxation, named convexified GNF (CGNF), obtains a globally optimal flow vector if the optimal injection vector is a Pareto point. More generally, the network can be decomposed into two subgraphs such that the lines between the subgraphs are congested at optimality and that CGNF finds correct optimal flows over all lines of one of these subgraphs. We also fully characterize the set of all globally optimal flow vectors, based on the optimal injection vector found via CGNF. In particular, we show that this solution set is a subset of the boundary of a convex set, and may include an exponential number of disconnected components. A primary application of this work is in optimization over electrical power networks.