= 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 an improving <graph cycle> pivot in the <network simplex algorithm>. This sign convention differs from the row-column potentials of a <transportation problem>.
Back to article page
