Minimum Cost Flow

What is a Minimum Cost Flow in a graph?

The minimum cost flow problem generalizes the maximum flow problem.

Let G be a directed graph. Let lcap and ucap be non-negative capacity functions on the edges such that 0<=lcap(e)<=ucap(e) for each edge e of G, and let cost be a cost function on the edges of G. Let supply be a function on the nodes of G. We talk about supply if supply(v)>0 and of demand if supply(v)<0 for a node v of G.

A flow in G must satisfy the capacity constraints, i.e., lcap(e)<=flow(e)<=ucap(e) for all edges e of G, and so-called mass balance constraints. The mass balance constraints state that, for each node v of G, the flow out of v minus the flow into v must equal supply(v). For every edge e of G, cost(e) is the cost of sending one unit of flow across the edge. The cost of a flow is the sum over flow(e)*cost(e) for all edges e of G. A minimum cost flow is a flow of minimum cost.

Intuition: We think of the graph as a flow network. Each directed edge in this network has a lower and upper bound on the amount of material that can be shipped over it. Each edge has also an associated cost for shipping one unit of the material over the edge. Each node in the network has a stated supply or demand of material. We want to ship material with minimum cost over the network from the nodes with supply to the nodes with demand in such a way that all capacity bounds of the edges are satisfied, and the flow out of a supply node equals its supply value and the flow into a demand node equals its demand.

Where can I use Minimum Cost Flow?

Algorithm for Minimum Cost Flow

MIN_COST_FLOW() is the name of the two LEDA function to compute a minimum cost flow in a directed graph.

Example of How to Use MIN_COST_FLOW()

Minimum Cost Maximum Flow

The minimum cost maximum flow problem is a combination of Maximum Flow Problem and the Minimum Cost Flow Problem. It asks for a maximum flow from a source node s to a target node t such that the total cost of the flow is minimum.

Example of How to Use MIN_COST_MAX_FLOW()

See also:

Graph Algorithms

Graphs and Related Data Types

Maximum Flow

Minimum Cut

Manual Entries: