# Minimum-cost flow problem

The minimum-cost flow problem is to find the cheapest possible way of sending a certain amount of flow through a flow network. Solving this problem is useful for real-life situations involving networks with costs associated (e.g. telecommunications networks), as well as in other situations where the analogy is not so obvious, such as where to locate warehouses.

## Definition

Given a flow network, that is, a directed graph $G=(V,E)$ with source s ∈ V and sink t ∈ V, where edge (u,v) ∈ E has capacity $c(u,v)>0$ , flow $f(u,v)\geq 0$ and cost $a(u,v)$ (most minimum-cost flow algorithms support edges with negative costs). The cost of sending this flow is $f(u,v)\cdot a(u,v)$ . You are required to send an amount of flow $d$ from s to t.

The definition of the problem is to minimize the total cost of the flow:

$\sum _{(u,v)\in E}a(u,v)\cdot f(u,v)$ with the constraints

## 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 $d$ .

The problem can be specialized into two other problems：

## Solutions

The minimum cost flow problem can be solved by linear programming, 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):

## Application

### Minimum weight bipartite matching

Given an bipartite graph G = (AB, E), we like to ﬁnd the maximum cardinality matching in G that has minimum cost. Let w: ER be a weight function on the edges of E. The minimum weight bipartite matching problem or assignment problem is to find a perfect matching ME whose total weight is minimized. The idea is to reduce this problem to a network flow problem.

Let G’ = (V’=AB, E’=E). Assign the capacity of all the edges in E’ to 1. Add a source vertex s and connect it to all the vertices in A’ and add a sink vertex t and connect all vertices inside group B’ to this vertex. The capacity of all the new edges is 1 and their costs is 0. It is proved that there is minimum weight perfect bipartite matching in G if and only if there a minimum cost flow in G’.