Minimum-cost flow

A minimum-cost flow minimizes a linear edge cost subject to vertex flow balances and edge capacity intervals. Subtracting every lower capacity from its edge flow converts all lower bounds to zero while shifting the balance vector and objective by constants.

For positive capacities and a feasible flow, optimality is equivalent to network dual potentials for which the network reduced cost is nonnegative at a lower bound, zero in the interior, and nonpositive at an upper bound. These signs make every feasible displacement nonnegative in total cost. They are also equivalent to absence of negative-cost cycles in the residual network. A zero-capacity edge is fixed and imposes no reduced-cost sign condition.

A flow balance prescribes net outgoing minus incoming flow at a vertex. Positive $b_i$ is supply and negative $b_i$ is demand; zero is ordinary flow conservation. Summing all balances requires total supply to equal total demand. In a directed graph, these equations are represented by the oriented incidence matrix.

An uncapacitated minimum-cost flow has nonnegative edge flows without finite upper capacities. The flow balances prescribe net supply at each vertex. For the oriented incidence matrix convention with tail $+1$ and head $-1$, vertex network dual potentials have network reduced costs $c_{ij}-{\pi }_i+{\pi }_j$. Nonnegative network reduced costs and complementary slackness certify a feasible optimum. A feasible negative-cost directed cycle makes the problem unbounded below.

A vertex potential in the dual of an uncapacitated minimum-cost flow yields the edge inequalities ${\pi }_i-{\pi }_j\le c_{ij}$. Its objective is ${\sum }_i{\pi }_i{b}_i$. Adding a common constant leaves all network reduced costs and the objective unchanged when total net supply is zero. Potentials tight on a spanning tree are fixed up to this common constant.

With the tail-positive incidence convention, a network edge's reduced cost is $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$. For uncapacitated minimum-cost flow, dual feasibility requires $r_{ij}\ge 0$ and complementary slackness requires $f_{ij}{r}_{ij}=0$. A negative non-tree reduced cost identifies an improving graph cycle pivot in the network simplex algorithm. This sign convention differs from the row-column potentials of a transportation problem.

The network simplex algorithm specializes the simplex algorithm to network flows. A basis is represented by a spanning tree with nonbasic flows at their bounds; potentials give reduced costs, and entering arcs produce cycle pivots. Degeneracy in linear programming is particularly common in assignment instances.

For a connected capacitated minimum-cost flow network, a spanning tree supplies basic flow variables. Every non-tree edge is fixed at its lower or upper bound. Flow balance determines the tree flows; these must also obey capacity constraints. An entering edge creates one cycle, and adjusting flow on that cycle preserves balance until a bound is hit and an edge leaves the tree.