In Linear Programming, I'm trying to answer the question:
For cycling to occur, is it required that the solution is degenerate?
In the SIMPLEX method, we say that a solution $x$ is degenerate if $x_i = 0$ for some $i$ in the basis.
Cycling is when one of the previously visited basis in the SIMPLEX algorithm, appears again before reaching the optimal solution.
My answer is that it doesn't have to. Meaning that cycling can occur without the solution being degenerate, but I can't come up with an explanation or a proof. I guess I could say so because after all the computations performed after each pivotting, there's no reason why the solution has to be degenerate again.
Best Answer
Yes, it has to be degenerate so that it “thinks” it can improve the solution by moving another variable into the basis. If that new solution is also degenerate and happens to take us to another degenerate solution that leads back to our original degenerate solution, then we have an infinite cycle.
See here as well: https://ocw.mit.edu/courses/sloan-school-of-management/15-053-optimization-methods-in-management-science-spring-2013/tutorials/MIT15_053S13_tut07.pdf