Minimum Cost Flow Problem

The minimum cost flow problem is related to many real world applications such as finding Wardrop equilibria in traffic networks.

Consider a strongly connected graph G=(V,E) without self loops and parallel edges. We denote n=|V| the number of vertices or nodes and m=|E| the number of links or edges. We want to find a flow x – a vector of shape (m, ) – that minimizes some objective cost function C:

min C(x)s.t.Γx=b,x0,

where show definitions:

Given a demand b, many flows x~X are feasible solutions. The minimum cost flow has lower cost compared to all other feasible flows: C(x)C(x~).

1. Undirected minimum cost flow problem

The classic minimum cost flow restricts quantities to traverse edges in one direction only. However, in many applications – physical networks such as gas, electrical or water networks – units may flow along the same edge in different directions. Solving the above optimization problem without the restriction x>0 thus yields the undirected minimum cost flow:

min C(x)s.t.Γx=b.

2. Multi-commodity minimum cost flow problem

Consider a n×k demand matrix B where each column represents a demand vector. Here, we want to find a n×k flow matrix X, where each column X:j is the minimum cost flow associated with the demand vector B:j. A minimum cost flow matrix is the solution to the following optimization problem:

min C(X)s.t.ΓX=B,X0

3. Characterization of minimum cost flows

3.1 Optimal potentials

A vector xRm is a minimum cost flow that solves the above optimization problem iff there is a vector πRn of vertex potentials so that:

fe(xe)πwπvfe+(xe) for all e=(v,w)E with xe>0,πwπvfe+(xe) for all e=(v,w)E with xe=0,

where show definitions:

The vector π is then termed optimal potential (vector). Optimal potentials can thus be used to verify if a flow x is indeed a minimum cost flow. If we can compute an optimal potential, x is a minimum cost flow; if no such potential exsits, it is not.

Potentials and direction of flow

Due to our convention for demand vectors b to encode sources with negative values and sinks with positive values, we define the potential difference πwπv, i.e., the potential increases in the direction of flow. This may not be intuitive for physical applications where quantities usually “flow” from higher to lower potential.