8.1 Networks and minimum-cost flows
A directed network has nodes \(1, \ldots , n\) and arcs \((i, j)\), each with a cost \(c_{ij}\) per unit of flow and a capacity \(u_{ij}\). Each node has a net supply \(b_i\) (positive at sources, negative at sinks, \(\sum b_i = 0\)). The minimum-cost flow problem is \[ \text {minimise } \sum _{(i,j)}c_{ij}x_{ij} \quad \text {subject to}\quad \sum _jx_{ij} - \sum _jx_{ji} = b_i \ \text {for every node } i, \quad 0 \leq x_{ij} \leq u_{ij} . \] The equations say that flow out minus flow in equals supply: conservation of flow. In matrix form they are \(Nx = b\), where the node–arc incidence matrix \(N\) has, in the column of arc \((i, j)\), a \(+1\) in row \(i\), a \(-1\) in row \(j\) and zeros elsewhere.
Theorem 8.1.1. The node–arc incidence matrix of a directed graph is totally unimodular. Hence, if the supplies and capacities are integers, the minimum-cost flow problem (if feasible and bounded) has an integral optimal solution.
Proof. Each column has one \(+1\) and one \(-1\). Put all the rows in one group in Theorem 7.4.3: every column has two non-zeros of opposite signs in the same group, as required. Integrality follows from Theorem 7.4.2, applied with the capacities as bounds. □
The transportation and assignment problems are minimum-cost flows on bipartite networks, and the shortest-path and maximum-flow problems below are further special cases. The network simplex method, in which bases are spanning trees exactly as in Proposition 7.1.1, solves the general problem many times faster than a general LP code.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.