Multi-commodity flow problem


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

Definition

Given a flow network, where edge has capacity. There are commodities, defined by, where and is the source and sink of commodity, and is its demand. The variable defines the fraction of flow along edge, where in case the flow can be split among multiple paths, and otherwise. Find an assignment of all flow variables which satisfies the following four constraints:
Link capacity: The sum of all flows routed over a link does not exceed its capacity.
Flow conservation on transit nodes: The amount of a flow entering an intermediate node is the same that exits the node.
Flow conservation at the source: A flow must exit its source node completely.
Flow conservation at the destination: A flow must enter its sink node completely.

Corresponding optimization problems

Load balancing is the attempt to route flows such that the utilization of all links is even, where
The problem can be solved e.g. by minimizing. A common linearization of this problem is the minimization of the maximum utilization, where
In the minimum cost multi-commodity flow problem, there is a cost for sending a flow on. You then need to minimize
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

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 and one sink. 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

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.
If fractional flows are allowed, the problem can be solved in polynomial time through linear programming, or through fully polynomial time approximation schemes.

External resources