Minimum cost flow problem
Encyclopedia
The minimum-cost flow problem is finding the cheapest possible way of sending a certain amount of flow through a flow network
.
with source 
and sink 
, where edge 
has capacity 
, flow 
and cost 
. The cost of sending this flow is 
. You are required to send an amount of flow 
from s to t.
The definition of the problem is to minimize the total cost of the flow:
with the constraints
With some solutions, finding the minimum cost maximum flow instead is straightforward. If not, you can do a binary search on
.
A related problem is the minimum cost circulation problem, which can be used for solving minimum cost flow. You do this by setting the lower bound on all edges to zero, and then make an extra edge from the sink
to the source 
, with capacity 
and lower bound 
, forcing the total flow from 
to 
to also be 
.
The problem can be specialized into two other problems：
, since we optimize a linear function, and all constraints are linear.
Apart from that, many combinatorial algorithms exist, for a comprehensive survey, see . Some of them are generalizations of maximum flow algorithms, others use entirely different approaches.
Well-known fundamental algorithms (they have many variations):
Flow network
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...
.
Definition
Given a flow network with source and sink , where edge has capacity , flow and cost . The cost of sending this flow is . You are required to send an amount of flow from s to t.The definition of the problem is to minimize the total cost of the flow:
with the constraints
| Capacity constraints: |  |
| Skew symmetry: |  |
| Flow conservation: |  |
| Required flow: |  |
Relation to other problems
A variation of this problem is to find a flow which is maximum, but has the lowest cost among the maximums. This could be called a minimum-cost maximum-flow problem. This is useful for finding minimum cost maximum matchings.With some solutions, finding the minimum cost maximum flow instead is straightforward. If not, you can do a binary search on
.A related problem is the minimum cost circulation problem, which can be used for solving minimum cost flow. You do this by setting the lower bound on all edges to zero, and then make an extra edge from the sink
to the source , with capacity and lower bound , forcing the total flow from to to also be .The problem can be specialized into two other problems：
- if the capacity constraint is removed, the problem is reduced to the shortest path problemShortest path problemIn graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized...
, - if the costs are all set equal to zero, the problem is reduced to the maximum flow problemMaximum flow problemIn optimization theory, the maximum flow problem is to find a feasible flow through a single-source, single-sink flow network that is maximum....
.
Solutions
The minimum cost flow problem can be solved by linear programmingLinear 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...
, since we optimize a linear function, and all constraints are linear.
Apart from that, many combinatorial algorithms exist, for a comprehensive survey, see . Some of them are generalizations of maximum flow algorithms, others use entirely different approaches.
Well-known fundamental algorithms (they have many variations):
- Cycle canceling: a general primal method.
- Minimum mean cycle canceling: a simple strongly polynomial algorithm.
- Successive shortest path and capacity scaling: dual methods, which can be viewed as the generalizations of the Ford–Fulkerson algorithm.
- Cost scaling: a primal-dual approach, which can be viewed as the generalization of the push-relabel algorithm.
- Network simplex: a specialized version of the linear programmingLinear programmingLinear 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...
simplex method.