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, with different source and sink nodes.

1 Definition
2 Relation to other problems
3 Usage
4 Solutions
5 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=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$
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=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}$

[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.

[edit] Usage

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

[edit] 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.

[edit] References

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