Why does degeneracy in a primal LP allow the algorithm to pivot indefinitely without changing the objective value, and how does Bland's rule prevent this cycling?
Welcome!
This community is for professionals and enthusiasts of our products and services.
Share and discuss the best content and new marketing ideas, build your professional profile and become a better marketer together.
This question has been flagged
Degeneracy creates basic variables with a value of zero. When such a variable is selected to leave the basis during a pivot, the maximum allowable step size along the search direction becomes zero. This causes the algorithm to swap basis variables without moving geometrically or altering the objective function value, potentially cycling indefinitely through the same set of degenerate bases.
Bland's rule prevents cycling by imposing a deterministic, anti-cycling tie-breaking criterion:
Entering Variable: Always select the non-basic variable with the smallest subscript among all variables eligible to enter (those with favorable reduced costs).
Leaving Variable: Always select the basic variable with the smallest subscript among all variables eligible to leave (those that attain the minimum ratio).
By strictly breaking ties using variable indices rather than arbitrary or objective-maximizing choices, Bland's rule eliminates symmetric, non-improving loops and guarantees finite termination.
Degeneracy occurs when a basic variable is zero. During a pivot, the basis can change while the objective value stays the same, allowing the Simplex method to return to a previous basis and cycle indefinitely. Bland’s rule prevents cycling by always choosing the variable with the smallest index among eligible entering variables and, in a tie, the smallest index among eligible leaving variables. This consistent tie-breaking prevents the algorithm from repeating the same basis indefinitely.
Enjoying the discussion? Don't just read, join in!
Create an account today to enjoy exclusive features and engage with our awesome community!
Sign up