= Capacitated flow optimality conditions
{title2=$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.
Back to article page
