Network reduced cost (source code)

= Network reduced cost
{title2=$r_{ij}=c_{ij}-\pi_i+\pi_j$}

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}\geq0$ and <complementary slackness> requires $f_{ij}r_{ij}=0$. A negative non-tree reduced cost identifies a candidate cost-decreasing <graph cycle> direction in the <network simplex algorithm>. This sign convention differs from the row-column potentials of a <transportation problem>.

A feasible positive step $\theta$ along that direction changes the objective by the corresponding negative <network reduced cost> times $\theta$. If a basic <flow> already lies at a blocking bound, the allowable step can instead be zero: that is a degenerate <network simplex algorithm> pivot, with no immediate objective decrease.