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

$\forall i\in K:\,\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.

$\forall i\in K:\,\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.

$\forall i\in K:\,\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 of the multi-commodity flow problem is a generalization of the minimum cost flow problem (in which there is merely one source $s$ and one sink $t$ . Variants of the circulation problem are generalizations of all flow problems. That is, any flow problem can be viewed as a particular circulation problem.

## 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, 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, or through (typically much faster) fully polynomial time approximation schemes.