Multi-commodity flow problem

The multi-commodity flow problem is a network flow problem with multiple commodities (or goods) flowing through the network, with different source and sink nodes.

Definition

Given a flow network $\,G(V,E)$, where edge $(u,v) \in E$ has 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=1}^{k} f_i(u,v) \leq c(u,v)$
Flow conservation:	$\,\sum_{w \in V} f_i(u,w) = 0 \quad \mathrm{when} \quad u \neq s_i, t_i$
	$\,\forall v, u,\, f_i(u,v) = -f_i(v,u)$
Demand satisfaction:	$\,\sum_{w \in V} f_i(s_i,w) = \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=1}^{k} f_i(u,v) \right)$

In the maximum multi-commodity flow problem, there are no hard demands on each commodity, but the total throughput is maximised:

$\sum_{i=1}^{k} \sum_{w \in V} f_i(s_i,w)$

In the maximum concurrent flow problem, the task is to maximise the minimal fraction of the flow of each commodity to its demand:

$\min_{1 \leq i \leq k} \frac{\sum_{w \in V} f_i(s_i,w)}{d_i}$

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.

Usage

RWA (Routing Wavelength Assignment) in Optical Burst Switching of Optical Network would be approached via multi-commodity flow formulas.

Solutions

The known solutions to this problem are based on linear programming^[1].

The problem is NP-complete^[2] for integer flows, even for only two commodities. There exist fully polynomial time approximation schemes for solving the problem within an error bound^[3]. For the fractional variant of the problem, a solution is found in polynomial time.

External resources

• Papers by Clifford Stein about this problem: http://www.columbia.edu/~cs2035/papers/#mcf
• Software solving the problem: http://www.zib.de/Optimization/Software/Mcf/

References

1. ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001) [1990]. "29". Introduction to Algorithms (2nd ed.). MIT Press and McGraw–Hill. pp. 788–789. ISBN 0-262-03293-7. 
2. ^ S. Even and A. Itai and A. Shamir (1976). "On the Complexity of Timetable and Multicommodity Flow Problems". SIAM Journal on Computing (SIAM) 5 (4): 691–703. doi:10.1137/0205048. http://link.aip.org/link/?SMJ/5/691/1. 
3. ^ George Karakostas (2002). "Faster approximation schemes for fractional multicommodity flow problems". Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. pp. 166–173. ISBN 0-89871-513-X.