Minimum cost flow problem

From Wikipedia, the free encyclopedia

The minimum cost flow problem is finding the cheapest possible way of sending a certain amount of flow through a flow network.

1 Definition
2 Relation to other problems
3 Solutions
4 References

[edit] Definition

Given a flow network $\,G(V,E)$ with source $s \in V$ and sink $t \in V$ , where edge $(u,v) \in E$ has capacity $\,c(u,v)$ , flow $\,f(u,v)$ , and the cost of sending this flow is $f(u,v) \cdot a(u,v)$ . You are required to send an amount of flow $\,d$ .

The definition^[1] of the problem is to minimise the total cost of the flow:

$\sum_{u,v \in V} a(u,v) \cdot f(u,v)$

with the constraints

Capacity constraints:	$\,f(u,v) \le c(u,v)$
Skew symmetry:	$\,f(u,v) = - f(v,u)$
Flow conservation:	$\,\sum_{w \in V} f(u,w) = 0$ for all $\,u \neq s, t$
Required flow:	$\,\sum_{w \in V} f(s,w) = d$

[edit] Relation to other problems

A variation of this problem is to find a flow which is maximum, but has the lowest cost among the maximums. This could be called a minimum cost maximum flow problem. This is useful for finding minimum cost maximum matchings.

With some solutions, finding the minimum cost maximum flow instead is straightforward. If not, you can do a binary search on $d$ .

A related and more general problem is the minimum cost circulation problem, which can be used for solving minimum cost flow. You do this by setting the lower bound on all edges to zero, and then make an extra edge from the sink $t$ to the source $s$ , with capacity $c (t, s) = d$ and lower bound $l (t, s) = d$ , forcing the total flow from $s$ to $t$ to also be $d$ .

[edit] Solutions

Minimum cost flow can be solved by linear programming, since we optimize a linear function, and all constraints are simple.

You can also use a modification of the Ford-Fulkerson algorithm, in which the search for an augmenting path is done by finding the shortest path in terms of the cost $k$ . You will have negative cost edges in this network, but you can use the Bellman-Ford algorithm, which handles this.