The multi-commodity flow problem is a network flow

Network flow

In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are...

 problem with multiple commodities (or goods) flowing through the network, with 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 the demand. The flow of commodity along edge is . Find an assignment of flow which satisfies the constraints:

Capacity constraints:
Flow conservation:
|
Demand satisfaction:

In the minimum cost multi-commodity flow problem, there is a cost for sending flow on . You then need to minimise


In the maximum multi-commodity flow problem, there are no hard demands on each commodity, but the total throughput is maximised:


In the maximum concurrent flow problem, the task is to maximise the minimal fraction of the flow of each commodity to its demand:

Relation to other problems

The minimum cost variant is a generalisation of the minimum cost flow problem

Minimum cost flow problem

The minimum-cost flow problem is finding the cheapest possible way of sending a certain amount of flow through a flow network.- Definition :Given a flow network \,G with source s \in V and sink t \in V, where edge \in E has capacity \,c, flow \,f and cost \,a. The cost of sending this flow is f...

. Variants of the circulation problem

Circulation problem

The circulation problem and its variants is a generalisation of network flow problems, with the added constraint of a lower bound on edge flows, and with flow conservation also being required for the source and sink...

 are generalisations of all flow problems.

Usage

RWA (Routing Wavelength Assignment)

Routing Wavelength Assignment (RWA)

The routing and wavelength assignment problem is a optical networking problem with the goal of maximizing the number of optical connections.- Definition :...

 in Optical Burst Switching

Optical burst switching

Optical burst switching is an optical networking technique that allows dynamic sub-wavelength switching of data. OBS is viewed as a compromise between the yet unfeasible full optical packet switching and the mostly static optical circuit switching...

 of Optical Network

Sonet

Sonet may refer to:* Sonet Records, European record label* Synchronous optical networking * Saab Sonett...

 would be approached via multi-commodity flow formulas.

Solutions

The known solutions to this problem are based on linear programming

Linear programming

Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...

.

The problem is NP-complete

NP-complete

In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

 for integer flows, even for only two commodities. There exist fully polynomial time approximation schemes for solving the problem within an error bound. For the fractional variant of the problem, a solution is found in polynomial time.

External resources

• Papers by Clifford Stein about this problem: http://www.columbia.edu/~cs2035/papers/#mcf
• Software solving the problem: http://www.zib.de/Optimization/Software/Mcf/