Minimum-cost flow problem

A flow network is a directed graph ${\displaystyle G=(V,E)}$ with a source vertex ${\displaystyle s\in V}$ and a sink vertex ${\displaystyle t\in V}$, where each edge ${\displaystyle (u,v)\in E}$ has capacity ${\displaystyle c(u,v)>0}$, flow ${\displaystyle f(u,v)}$ and cost ${\displaystyle a(u,v)}$, with most minimum-cost flow algorithms supporting edges with negative costs. The cost of sending this flow along an edge ${\displaystyle (u,v)}$ is ${\displaystyle f(u,v)\cdot a(u,v)}$. The problem requires an amount of flow ${\displaystyle d}$ to be sent from source ${\displaystyle s}$ to sink ${\displaystyle t}$.

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

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

with the constraints

Capacity constraints:	${\displaystyle \,f(u,v)\leq c(u,v)}$
Skew symmetry:	${\displaystyle \,f(u,v)=-f(v,u)}$
Flow conservation:	${\displaystyle \,\sum _{w\in V}f(u,w)=0{\text{ for all }}u\neq s,t}$
Required flow:	${\displaystyle \,\sum _{w\in V}f(s,w)=d{\text{ and }}\sum _{w\in V}f(w,t)=d}$

A variation of this problem is to find a flow which is maximum, but has the lowest cost among the maximum flow solutions. This could be called a minimum-cost maximum-flow problem and is useful for finding minimum cost maximum matchings.

With some solutions, finding the minimum cost maximum flow instead is straightforward. If not, one can find the maximum flow by performing a binary search on ${\displaystyle d}$.

A related problem is the minimum cost circulation problem, which can be used for solving minimum cost flow. This is achieved by setting the lower bound on all edges to zero, and then making an extra edge from the sink ${\displaystyle t}$ to the source ${\displaystyle s}$, with capacity ${\displaystyle c(t,s)=d}$ and lower bound ${\displaystyle l(t,s)=d}$, forcing the total flow from ${\displaystyle s}$ to ${\displaystyle t}$ to also be ${\displaystyle d}$.

The following problems are special cases of the minimum cost flow problem (we provide brief sketches of each applicable reduction, in turn):[1]

• Shortest path problem (single-source). Require that a feasible solution to the minimum cost flow problem sends one unit of flow from a designated source ${\displaystyle s}$ to a designated sink ${\displaystyle t}$. Give all edges infinite capacity.
• Maximum flow problem. Let all nodes have zero demand, and let the cost associated with traversing any edge be zero. Now, introduce a new edge ${\displaystyle (t,s)}$ from the current sink ${\displaystyle t}$ to the current source ${\displaystyle s}$. Stipulate that the per-unit cost of sending flow across edge ${\displaystyle (t,s)}$ equals ${\displaystyle -1}$, and permit ${\displaystyle (t,s)}$ infinite capacity. (This reduction is also mentioned in Circulation problem).
• Assignment problem. Suppose that each partite set in the bipartition has ${\displaystyle n}$ vertices, and denote the bipartition by ${\displaystyle (X,Y)}$. Give each ${\displaystyle x\in X}$ supply ${\displaystyle 1/n}$ and give each ${\displaystyle y\in Y}$ demand ${\displaystyle 1/n}$. Each edge is to have unit capacity.

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):

• Cycle canceling: a general primal method.
• Cut canceling: a general dual method.
• Minimum mean cycle canceling: a simple strongly polynomial algorithm.
• Successive shortest path and capacity scaling: dual methods, which can be viewed as the generalization 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 algorithm: a specialized version of the linear programming simplex method.
• Out-of-kilter algorithm by D. R. Fulkerson

• LEMON (C++ library)
• GNU Linear Programming Kit
• Network flow problem

1. ^ Ravindra K. Ahuja; Thomas L. Magnanti & James B. Orlin (1993). Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc. ISBN 978-0-13-617549-0.
2. ^ Morton Klein (1967). "A primal method for minimal cost flows with applications to the assignment and transportation problems". Management Science. 14 (3): 205–220. CiteSeerX 10.1.1.228.7696. doi:10.1287/mnsc.14.3.205.
3. ^ Refael Hassin (1983). "The minimum cost flow problem: A unifying approach to existing algorithms and a new tree search algorithm". Mathematical Programming. 25: 228–239. doi:10.1007/bf02591772.
4. ^ Thomas R. Ervolina & S. Thomas McCormick (1993). "Two strongly polynomial cut cancelling algorithms for minimum cost network flow". Discrete Applied Mathematics. 4: 133–165. doi:10.1016/0166-218x(93)90025-j.
5. ^ Andrew V. Goldberg & Robert E. Tarjan (1989). "Finding minimum-cost circulations by canceling negative cycles". Journal of the ACM. 36 (4): 873–886. doi:10.1145/76359.76368.
6. ^ Jack Edmonds & Richard M. Karp (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM. 19 (2): 248–264. doi:10.1145/321694.321699.
7. ^ Andrew V. Goldberg & Robert E. Tarjan (1990). "Finding minimum-cost circulations by successive approximation". Math. Oper. Res. 15 (3): 430–466. doi:10.1287/moor.15.3.430.
8. ^ James B. Orlin (1997). "A polynomial time primal network simplex algorithm for minimum cost flows". Mathematical Programming. 78 (2): 109–129. doi:10.1007/bf02614365. hdl:1721.1/2584.

• LEMON C++ library with several maximum flow and minimum cost circulation algorithms
• The MCFClass C++ project library with some minimum cost flow and shortest path algorithms