Minimum-cost flow problem can be formulated by linear programming as follows:
The inputs contain an n by m matrix A, in which each column has only two non-zero entries and one is 1 and another one is -1, a cost vector c with length m, a constraint vector b with length n, a lower bound vector l with length m, and an upper bound vector u with length m, where 0 ≤ l ≤ u.
Variables form a length m vector f. The problem is 
This is the most general form, as long as the problem can be transformed into this form, this problem can be solved by network flow algorithm. There is no general way to detect a linear program can be transformed into a min cost flow problem. However, there are several algorithms that can transform a certain class of linear program into min cost flow problem[1].
The relation between this LP formulation and graph representation for network is as follows. The matrix A is just incidence matrix of the graph: each row corresponds to a node. Each column corresponds to a directed edge, since there is one +1 entry and one -1 entry in each column. The constraint vector b is the supply/demand for each node and the lower bound and upper bound constraints apply to each edge.
We usually consider directed graph only. When the graph is undirected with non-negative cost, then we can transform the graph into a directed graph. However, if there are negative edge costs, there is another transformation should be made[3]. For undirected graphs, if there are upper/lower bound on the flow, the problem becomes NP-Hard[4].
There are several related problems:
- Minimum cost circulation problem: The constraint vector b is zero.
- Transshipment problem: The lower bound l is zero and the upper bound u is infinity.
- Transportation problem: The underlying graph is a bipartite graph. That is the nodes is the union of two sets U and V, and directed edges only point from U to V with zero lower bound.
- Assignment problem: Same as transportation problem but
.
Maximum flow problem and shortest path problem are also special cases of minimum cost flow as well.
As it turns out, the minimum cost flow problem is equivalent to minimum cost circulation problem and transshipment problem in the sense that they can be reduce to each other while blowing up the input size by a constant factor. Min cost flow problem can also be reduced to transportation problem, but the size of A may blow up polynomially. Transportation problem can also be reduced to assignment problem, but the size of A may blow up exponentially.
Thus, in order to solve min cost flow problem efficiently in theory, it suffices to solve min cost circulation problem or transshipment problem efficiently.
There are several algorithms that can solve min cost flow problem, like shortest augmenting path, cycle canceling, scaling, and network simplex. Some of them are strongly polynomial time. According to [2], the most practical algorithm is the network simplex method.
For series-parallel graphs, finding min-cost flow can be done in O(n lg n) time.
Reference:
[1] Robert E. Bixby and Donald K. Wagner, “An almost linear-time algorithm for graph realization,” Mathematics of Operations Research Volume 13 Issue 1, February 1988 Pages 99 – 123.
[2] Péter Kovácsab, “Minimum-cost flow algorithms: an experimental evaluation,” Optimization Methods and Software Volume 30, Issue 1, February 2015 Pages 94-127
[3] A. Sedeño-Noda, C. González-Martín, S. Alonso, Solving the undirected minimum cost flow problem with arbitrary costs, Networks Volume 45 Issue 1, January 2005
[4] Alon Itai, Two-Commodity Flow, Journal of the ACM Volume 25 Issue 4, Oct. 1978
Algorithms Notes 