# Convex Network Flows

**Authors:** Theo Diamandis, Guillermo Angeris, Alan Edelman  
**arXiv:** [2404.00765](https://arxiv.org/abs/2404.00765)  
**Date:** 2024-03-31  
**Summary page:** https://www.summarizepaper.com/en/paper/2404.00765v1/

## Key points

- Authors Theo Diamandis, Guillermo Angeris, and Alan Edelman introduce a framework for convex network flows over hypergraphs
- The convex flow problem incorporates concave utility functions for net flow at nodes and flow along edges
- Objective is to minimize combined utilities while adhering to constraints on allowable flows within a convex set
- Framework addresses traditional network optimization challenges like max flow, min-cost flow, and multi-commodity flows
- Extends problems to accommodate scenarios like concave edge gain functions
- Applications include optimal power flow, routing in wireless networks, Arrow-Debreu Nash bargaining, and order routing through financial exchanges
- Convex flow problem has a dual with multiple interpretations that decomposes over edges of the hypergraph
- Efficient solution algorithm parallelizes across edges and offers streamlined interface
- Open-source implementation in Julia programming language outperforms commercial solver Mosek in terms of speed

## Summary

In their paper titled "Convex Network Flows," authors Theo Diamandis, Guillermo Angeris, and Alan Edelman introduce a comprehensive framework for addressing flow problems over hypergraphs. The formulation, referred to as the convex flow problem, incorporates concave utility functions for both the net flow at every node and the flow along each edge. The primary objective is to minimize the combined utilities while adhering to constraints on allowable flows at each edge within a convex set. This innovative framework encompasses traditional network optimization challenges such as max flow, min-cost flow, and multi-commodity flows. It also extends these problems to accommodate complex scenarios like concave edge gain functions. The applications of this framework span various domains including optimal power flow in lossy networks, routing and resource allocation in ad-hoc wireless networks, Arrow-Debreu Nash bargaining, and order routing through financial exchanges. The authors demonstrate that the convex flow problem possesses a dual with multiple intriguing interpretations that decomposes over the edges of the hypergraph. Leveraging this decomposition, they propose an efficient solution algorithm that parallelizes across edges and offers a streamlined problem interface. Additionally, they provide an open-source implementation of this algorithm in the Julia programming language which showcases its superior speed compared to leading commercial convex solver Mosek. Overall,this research significantly advances the understanding and practical application of convex network flows by offering a versatile framework that can address a wide range of real-world optimization challenges across diverse fields.