Convex Flow Problem

Optimizing over graphs embedding physics

Flows bend; costs curve. Packets, pipes, prices, power. Graphs capture the physics.

Problem: choose edge flows on a graph to minimize total network and edge costs, subject to node balance and edge feasibility (including hyperedges).

This unifies max-flow, min-cost, and more. Variations show up across many applications:

🔹 Traffic and packet routing with congestion

🔹 Cryptoasset order routing with price impact

🔹 Optimal power flow with convex relaxations

🔹 Water/gas pipeline with frictional losses

⸻

📚 Further Reading

This post was inspired by a few papers by G. Angeris and T. Diamandis. Note I present it here a little differently than in their work.

arXiv links:

- https://arxiv.org/pdf/2404.00765

- https://arxiv.org/pdf/2408.12761

- https://arxiv.org/pdf/2408.11040