| dc.description.abstract | This thesis introduces a new framework for flow problems over hypergraphs. Our problem formulation, which we call the convex flow problem, only assumes that the constraints on the flows over each edge are in some convex set. The objective is to maximize a sum of concave utility functions---one for the net flow at every node and one for each edge flow---subject to these constraints. 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. As a result, 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. This problem has a number of interesting properties, including a 'calculus' of flow sets, an equivalent conic form, and a natural generalization of many classic network flow results.
We develop an efficient algorithm for solving the convex flow problem by constructing a particular dual problem that decomposes over the edges of the hypergraph. This dual problem has a number of useful interpretations and admits a straightforward specification: the dual function and its gradient can be evaluated using only simple subroutines which often have closed-form solutions. These subroutines suggest a clean, easy-to-use problem interface, which we provide in the open-source software package ConvexFlows.jl, written in the Julia programming language. We discuss implementation considerations, including how to handle important special cases, and we provide a simple interface for specifying convex flow problems. We show that our solver is significantly faster than the state-of-the-art commercial optimization solver Mosek, even for small problems sizes with limited parallelization.
Finally, we consider the nonconvex flow problem with fixed costs on the edges, i.e., where there is some fixed cost to send any nonzero flow over an edge. We show that this problem has almost integral solutions by a Shapley--Folkman argument, and we provide a simple modification of our original algorithm for this nonconvex problem. We conclude by discussing a number of interesting avenues for future work. | |
