Multi-commodity flow problem

From Wikipedia, the free encyclopedia

The multi-commodity flow problem is a network flow problem with multiple commodities (or goods) flowing through the network.

1 Definition
2 Relation to other problems
3 Solutions
4 References

[edit] Definition

Given a flow network $\,G(V,E)$ , where edge $(u,v) \in E$ capacity $c (u, v)$ . There are $k$ commodities $K_1,K_2,\dots,K_k$ , defined by $K i = (s i, t i, d i)$ , where $s i$ and $t i$ is the source and sink of commodity $i$ , and $d i$ is the demand. The flow of commodity $i$ along edge $(u, v)$ is $f i (u, v)$ . Find an assignment of flow which satisfies the constraints:

Capacity constraints:	$\,\sum_i f_i(u,v) \leq c(u,v)$
Skew symmetry:	$\,f_i(u,v) = - f_i(v,u)$
Flow conservation:	$\,\sum_{w \in V} f_i(u,w) = 0 \quad \mathrm{when} \quad u \neq s_i, t_i$
Demand satisfaction:	$\,\sum_{w \in V} f_i(s_i,w) = d_i \Leftrightarrow \sum_{w \in V} f_i(w,t_i) = d_i$

In the minimum cost multi-commodity flow problem, there is a cost $a(u,v) \cdot f(u,v)$ for sending flow on $(u, v)$ . You then need to minimise

$\sum_{(u,v) \in E} \left( a(u,v) \sum_i f_i(u,v) \right)$

[edit] Relation to other problems

The minimum cost variant is a generalisation of the minimum cost flow problem. Variants of the circulation problem are generalisations of all flow problems.