Capacitated flow optimality conditions ($r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$)

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.