A vertex potential in the dual of an uncapacitated minimum-cost flow yields the edge inequalities . Its objective is . Adding a common constant leaves all network reduced costs and the objective unchanged when total net supply is zero. Potentials tight on a spanning tree are fixed up to this common constant.
In a directed network with no negative-cost directed cycle, add a source having zero-cost arcs to all vertices and compute shortest-path distances . The inequalities make dual feasible for uncapacitated minimum-cost flow. Shortest-path tree arcs are tight. An arbitrary spanning tree also fixes tight candidate potentials up to a constant, but it does not guarantee the non-tree inequalities; these must be checked.
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.