Consider an assignment problem with sources 1, 2, 3, 4 and sinks 5, 6, 7, 8. There is an arc between each source and each sink. The arc costs are as follows:
Suppose that the simplex method is applied without restriction on the choice of the out-arc (so the generated trees need not be strongly feasible). Verify that one possible sequence of in-arc/out-arc pairs is given by
and that after these twelve pivots we obtain the initial tree again. (This example comes from Chvatal [1983].)
Already registered? Login
Not Account? Sign up
Enter your email address to reset your password
Back to Login? Click here