Flow networks #

A flow network is a nice way to model things that flow between nodes through edges of different capacities. It is surprisingly flexible and used in all sorts of places where you might not necessarily expect it. It’s a very intuitive and beautiful idea.

The minimum cost flow problem, the optimisation problem of finding a flow through a flow network with the minimal cost, is a well-known special case of a integer linear program that can be solved in polynomial time with a variety of algorithms.

  • This introduction to network flow, an interesting graph theory concept I’d forgotten about.
  • A very fast algorithm for solving the minimum cost flow problem, from 1992.
  • A nice paper describing an almost-linear time algorithm for solving the minimum cost flow problem (and the equivalent maximum flow problem), from 2022.
  • OR-tools (note) implementation of a MCF solver.