Multi-commodity flow problem

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

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}$

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)$

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.

Solutions

The only known solution to this problem is linear programming.