# 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 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 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, 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

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]

## References

1. ^ 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.
2. ^ 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.
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.