On page 5 of the slide,

[T]he reduced cost of a non-basic arc $(i, j)$ is the sum of the costs of the arcs forming a cycle with $(i, j)$ in the current tree solution.

Why is that the case?


1 Answer 1


http://www.unc.edu/depts/stat-or/courses/provan/STOR724_web/lect14_simp.pdf (bottom of page 13)

It's the sum of costs but directed consistent with (i,j), i.e. if the arc is going in the same direction as (i,j), it counts as positive, and is negative otherwise. It makes more sense that way since you want to add arcs that create negative cycles in order to decrease the overall cost.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .