With the tail-positive incidence convention, a network edge's reduced cost is . For uncapacitated minimum-cost flow, dual feasibility requires and complementary slackness requires . 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 along that direction changes the objective by the corresponding negative network reduced cost times . 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.

Articles by others on the same topic (0)

There are currently no matching articles.