Thread: simplex algorithm:can leaving variable enter the basis again?

hi.
Is it possible that variable Xi leaves the basis and enter the basis again in the next step? what about other steps (not next to current step)?

In each step of simplex algorithm, exactly one variable leaves the basis and exactly another one enter the basis. That said, if the same variable leaves and enter the basis in subsequent steps, then the basis dont change, and the algorithm enters in infinite loop. I dont remember exactly how simplex works, but supposing that simplex is correct, then this case cannot happen. On the other hand, it is completely normal the same variable leave the basis and then, in a future step, enters the basis again. Remember, the simplex is an exponential time algorithm, and its worst running time is determined by the number of different basis it has. Therefore, if a variable leaves the basis and never comes back, then simplex would quickly run out of variables to enter the basis, and then it would be a polinomial time algorithm.

BUT!! I remember that there was some king of "degenerate cases" that could bring problems to simplex functioning, but right now i dont remeber exactly what are these "degenerate cases".