Convex Network Flows

Résumé : We introduce a general framework for flow problems over hypergraphs. In our problem formulation, which we call the convex flow problem, we have a concave utility function for the net flow at every node and a concave utility function for each edge flow. The objective is to minimize the sum of these utilities, subject to constraints on the flows allowed at each edge, which we only assume to be a convex set. This framework not only includes many classic problems in network optimization, such as max flow, min-cost flow, and multi-commodity flows, but also generalizes these problems to allow, for example, concave edge gain functions. In addition, our framework includes applications spanning a number of fields: optimal power flow over lossy networks, routing and resource allocation in ad-hoc wireless networks, Arrow-Debreu Nash bargaining, and order routing through financial exchanges, among others. We show that the convex flow problem has a dual with a number of interesting interpretations, and that this dual decomposes over the edges of the hypergraph. Using this decomposition, we propose a fast solution algorithm that parallelizes over the edges and admits a clean problem interface. We provide an open source implementation of this algorithm in the Julia programming language, which we show is significantly faster than the state-of-the-art commercial convex solver Mosek.