Algorithms in a Nutshell

Minimum Cost Flow

To solve a Minimum Cost Flow problem we need only construct a flow network graph and ensure that it satisfies the criteria discussed earlier—capacity constraint, flow conservation, and skew symmetry—as well as two additional criteria:

Supply satisfaction

For each source vertex s_i∈S, the sum of f(s_i,v) for all edges (s_i,v)∈E (the flow out of s_i) minus the sum of f(u, s_i) for all edges (u, s_i)∈E (the flow into s_i) must be less than or equal to sup(s_i). That is, the supply sup(s_i) at each source vertex is a firm upper bound on the net flow from that vertex.

Demand satisfaction

For each sink vertex t_j∈T, the sum of f(u, t_j) for all edges (u, t_j)∈E (the flow into t_j) minus the sum of f(t_j,v) for all edges (t_j,v)∈E (the flow out of t_j) must be less than or equal to dem(t_j). That is, the dem(t_j) at each target vertex is a firm upper bound on the net flow into that vertex.

To simplify the algorithmic solution, we further constrain the flow network graph to have a single source vertex and sink vertex. This can be easily accomplished by taking an existing flow network graph with any number of source and sink vertices and adding two new vertices. First, add a new vertex (which we refer to as s₀) to be the source vertex for the flow network graph, and add edges (s₀,s_i) for all s_i∈S whose capacity c(s₀,s_i)=sup(s_i) and whose cost d(s₀,s_i)=0. Second, add a new vertex (which we often refer to as tgt, for target) to be the sink vertex for the flow network graph, and add edges ( ...