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 without self loops and parallel edges.
We denote the number of vertices or nodes and the number of links
or edges.
We want to find a flow – a vector of shape (m, ) – that minimizes some
objective cost function :
is the
incidence matrix of and
a demand vector of shape (n, ) that encodes the demand values for each node,
negative values representing sources.
Given a demand , many flows are
feasible solutions.
The minimum cost flow has lower cost compared to all other feasible flows:
.
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 thus yields the
undirected minimum cost flow:
Consider a demand matrix where each column represents a
demand vector. Here, we want to find a flow matrix , where
each column is the minimum cost flow associated with the demand vector
. A minimum cost flow matrix is the solution to the following optimization
problem:
A vector is a minimum cost flow that solves the above optimization problem iff
there is a vector of vertex potentials so that:
is piecewise linear marginal cost function,
denotes the left-hand limit of , and
the right-hand limit of .
The vector is then termed optimal potential (vector).
Optimal potentials can thus be used to verify if a flow is indeed a minimum cost flow.
If we can compute an optimal potential, 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 to encode sources with negative values and sinks
with positive values, we define the potential difference , 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.