Multi-commodity flow problem

The multi-commodity flow problem is a network flow problem with multiple commodities (flow demands) between 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 its demand. The variable $\,f_{i}(u,v)$ defines the fraction of flow $\,i$ along edge $\,(u,v)$ , where $\,f_{i}(u,v)\in [0,1]$ in case the flow can be split among multiple paths, and $\,f_{i}(u,v)\in \{0,1\}$ otherwise (i.e. "single path routing"). Find an assignment of all flow variables which satisfies the following four constraints:

(1) Link capacity: The sum of all flows routed over a link does not exceed its capacity.

\forall (u,v)\in E:\,\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\leq c(u,v)

(2) Flow conservation on transit nodes: The amount of a flow entering an intermediate node $u$ is the same that exits the node.

\,\sum _{w\in V}f_{i}(u,w)-\sum _{w\in V}f_{i}(w,u)=0\quad \mathrm {when} \quad u\neq s_{i},t_{i}

(3) Flow conservation at the source: A flow must exit its source node completely.

\,\sum _{w\in V}f_{i}(s_{i},w)-\sum _{w\in V}f_{i}(w,s_{i})=1

(4) Flow conservation at the destination: A flow must enter its sink node completely.

\,\sum _{w\in V}f_{i}(w,t_{i})-\sum _{w\in V}f_{i}(t_{i},w)=1

Corresponding optimization problems

Load balancing is the attempt to route flows such that the utilization $U(u,v)$ of all links $(u,v)\in E$ is even, where

U(u,v)={\frac {\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}}{c(u,v)}}

The problem can be solved e.g. by minimizing $\sum _{u,v\in V}(U(u,v))^{2}$ . A common linearization of this problem is the minimization of the maximum utilization $U_{max}$ , where

\forall (u,v)\in E:\,U_{max}\geq U(u,v)

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

\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, the demand of each commodity is not fixed, and the total throughput is maximized by maximizing the sum of all demands $\sum _{i=1}^{k}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

Routing and wavelength assignment (RWA) in optical burst switching of Optical Network would be approached via multi-commodity flow formulas.

Solutions

In the decision version of problems, the problem of producing an integer flow satisfying all demands is NP-complete,^[1] even for only two commodities and unit capacities (making the problem strongly NP-complete in this case).

If fractional flows are allowed, the problem can be solved in polynomial time through linear programming.^[2] Or through (typically much faster) fully polynomial time approximation schemes.^[3]

External resources

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

References

↑ 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. Retrieved 2016-10-05.
↑ 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.
↑ 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.