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.

Given a flow network ${\displaystyle ,円G(V,E)}${\displaystyle ,円G(V,E)}, where edge ${\displaystyle (u,v)\in E}${\displaystyle (u,v)\in E} has capacity ${\displaystyle ,円c(u,v)}${\displaystyle ,円c(u,v)}. There are ${\displaystyle ,円k}${\displaystyle ,円k} commodities ${\displaystyle K_{1},K_{2},\dots ,K_{k}}${\displaystyle K_{1},K_{2},\dots ,K_{k}}, defined by ${\displaystyle ,円K_{i}=(s_{i},t_{i},d_{i})}${\displaystyle ,円K_{i}=(s_{i},t_{i},d_{i})}, where ${\displaystyle ,円s_{i}}${\displaystyle ,円s_{i}} and ${\displaystyle ,円t_{i}}${\displaystyle ,円t_{i}} is the source and sink of commodity ${\displaystyle ,円i}${\displaystyle ,円i}, and ${\displaystyle ,円d_{i}}${\displaystyle ,円d_{i}} is its demand. The variable ${\displaystyle ,円f_{i}(u,v)}${\displaystyle ,円f_{i}(u,v)} defines the fraction of flow ${\displaystyle ,円i}${\displaystyle ,円i} along edge ${\displaystyle ,円(u,v)}${\displaystyle ,円(u,v)}, where ${\displaystyle ,円f_{i}(u,v)\in [0,1]}${\displaystyle ,円f_{i}(u,v)\in [0,1]} in case the flow can be split among multiple paths, and ${\displaystyle ,円f_{i}(u,v)\in \{0,1\}}${\displaystyle ,円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.

${\displaystyle \forall (u,v)\in E:,円\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\leq c(u,v)}${\displaystyle \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 ${\displaystyle u}${\displaystyle u} is the same that exits the node.

${\displaystyle \forall i\in \{1,\ldots ,k\}:,円\sum _{(u,w)\in E}f_{i}(u,w)-\sum _{(w,u)\in E}f_{i}(w,u)=0\quad \mathrm {when} \quad u\neq s_{i},t_{i}}${\displaystyle \forall i\in \{1,\ldots ,k\}:,円\sum _{(u,w)\in E}f_{i}(u,w)-\sum _{(w,u)\in E}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.

${\displaystyle \forall i\in \{1,\ldots ,k\}:,円\sum _{(u,w)\in E}f_{i}(s_{i},w)-\sum _{(w,u)\in E}f_{i}(w,s_{i})=1}${\displaystyle \forall i\in \{1,\ldots ,k\}:,円\sum _{(u,w)\in E}f_{i}(s_{i},w)-\sum _{(w,u)\in E}f_{i}(w,s_{i})=1}

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

${\displaystyle \forall i\in \{1,\ldots ,k\}:,円\sum _{(u,w)\in E}f_{i}(w,t_{i})-\sum _{(w,u)\in E}f_{i}(t_{i},w)=1}${\displaystyle \forall i\in \{1,\ldots ,k\}:,円\sum _{(u,w)\in E}f_{i}(w,t_{i})-\sum _{(w,u)\in E}f_{i}(t_{i},w)=1}

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

${\displaystyle U(u,v)={\frac {\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}}{c(u,v)}}}${\displaystyle 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 ${\displaystyle \sum _{u,v\in V}(U(u,v))^{2}}${\displaystyle \sum _{u,v\in V}(U(u,v))^{2}}. A common linearization of this problem is the minimization of the maximum utilization ${\displaystyle U_{max}}${\displaystyle U_{max}}, where

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

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

${\displaystyle \sum _{(u,v)\in E}\left(a(u,v)\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\right)}${\displaystyle \sum _{(u,v)\in E}\left(a(u,v)\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\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 ${\displaystyle \sum _{i=1}^{k}d_{i}}${\displaystyle \sum _{i=1}^{k}d_{i}}

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 ${\displaystyle s}${\displaystyle s} and one sink ${\displaystyle t}${\displaystyle 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.^[1]

Routing and wavelength assignment (RWA) in optical burst switching of Optical Network would be approached via multi-commodity flow formulas, if the network is equipped with wavelength conversion at every node.

Register allocation can be modeled as an integer minimum cost multi-commodity flow problem: Values produced by instructions are source nodes, values consumed by instructions are sink nodes and registers as well as stack slots are edges.^[2]

In the decision version of problems, the problem of producing an integer flow satisfying all demands is NP-complete,^[3] 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,^[4] or through (typically much faster) fully polynomial time approximation schemes.^[5]

Multicommodity flow is applied in the overlay routing in content delivery.^[6]

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

Add: Jean-Patrice Netter, Flow Augmenting Meshings: a primal type of approach to the maximum integer flow in a multi-commodity network, Ph.D dissertation Johns Hopkins University, 1971

• Network flow problem
• NP-complete problems

• CS1 maint: multiple names: authors list
• Articles with short description
• Short description is different from Wikidata