Min-cost flow problem

Basic definitions

1. Basic graph definitions
2. Basic flow definitions

Input

1. A simple, anti-symmetric directed graph [math]\displaystyle{ G=(V,A) }[/math].
2. For each arc [math]\displaystyle{ a\in A }[/math], there are two real numbers:
   1. The upper bound (ak.a. capacity) [math]\displaystyle{ u(a)\geq 0 }[/math].
   2. The (unit) cost or cost factor [math]\displaystyle{ c(a)\geq 0 }[/math].
3. For each node [math]\displaystyle{ v\in V }[/math], there is a real-valued balance [math]\displaystyle{ b(v) }[/math].

Prerequisite for feasibility: [math]\displaystyle{ \sum_{v\in V}b(v)=0 }[/math].

Output

A min-cost flow [math]\displaystyle{ f }[/math], that is, a real number [math]\displaystyle{ f(a) }[/math] for each arc [math]\displaystyle{ a\in A }[/math] such that:

1. Capacity constraints: [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math] for all [math]\displaystyle{ a\in A }[/math].
2. Flow conservation condition: For each node [math]\displaystyle{ v\in V }[/math], it is [math]\displaystyle{ \sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)=b(v) }[/math].
3. Optimality: The cost of [math]\displaystyle{ f }[/math], [math]\displaystyle{ c(f):=\sum_{a\in A}c(a)\cdot f(a) }[/math], is minimum among all flows that satisfy the capacity constraints and the flow conservation condition.

Negative cost factors

The case that some arcs have negative cost factors, may be transformed as follows into the above version, in which all cost factors are nonnegative. For each arc [math]\displaystyle{ a=(v,w) }[/math] such that [math]\displaystyle{ c(a)\lt 0 }[/math]:

1. Turn [math]\displaystyle{ a }[/math], giving a new arc [math]\displaystyle{ a'=(w,v) }[/math].
2. Set [math]\displaystyle{ u(a'):=u(a) }[/math] and [math]\displaystyle{ c(a'):=-c(a) }[/math].
3. Decrease [math]\displaystyle{ b(v) }[/math] by [math]\displaystyle{ u(a) }[/math] and increase [math]\displaystyle{ b(w) }[/math] by [math]\displaystyle{ u(a) }[/math].
4. The resulting flow [math]\displaystyle{ f(a') }[/math] on [math]\displaystyle{ a' }[/math] is transformed back into [math]\displaystyle{ f(a):=u(a)-f(a') }[/math].

Recall that the original graph [math]\displaystyle{ G }[/math] is simple, so the resulting graph is still simple.

Known Algorithms

1. Negative cycle-canceling
2. Successive shortest paths
3. Successive shortest paths with reduced costs