---
title: Multi-commodity flow problem
slug: multi-commodity-flow-problem
qid: Q6934437
snapshot: multi-commodity-flow-problem-781700-123f39f1d6d08b4d
content_hash: 123f39f1d6d08b4d1551944c1c3d86ee1fbfa30f78b928ac8c7b55059ff86503
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1346580435
tags: [10639794, 23118434, 23603337, 29176510, 29265124]
---

# Multi-commodity flow problem

> [!note] Provenance
> Snapshot `multi-commodity-flow-problem-781700-123f39f1d6d08b4d` · content root `123f39f1d6d08b4d…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1346580435> · Licensed CC BY-SA 4.0

The multi-commodity flow problem is a network flow problem with multiple commodities (flow demands) between different source and sink nodes.

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\{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. \forall i\in\{1,\ldots,k\}:\,\sum_{(s_i,w) \in E} f_i(s_i,w) - \sum_{(w,s_i) \in E} f_i(w,s_i) = 1 (4) Flow conservation at the destination: A flow must enter its sink node completely. \forall i\in\{1,\ldots,k\}: \,\sum_{(w,t_i) \in E} f_i(w,t_i) - \sum_{(t_i,w) \in E} 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)\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 \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, 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. ==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. ==Applications== Multicommodity flow is applied in the overlay routing in content delivery. ==External resources== 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/ ==References== 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
