About cycling in simplex method

927 Views Asked by At

First of all I apologize if you find my question silly as I am not a student from math background.

So far I know when the same basic variables reappear in a later iteration, we say that cycling occurs. My question is: Suppose in one iteration, $x_{1}, x_{2}, x_{3}$ are basic variables, and after some iteration $x_{1}, x_{7}, x_{8}$ appears as basic variables. Since $x_{1}$ is getting repeated can we say that this is also a cycling?

1

There are 1 best solutions below

0
On

Effectively, this has been answered already by @Mark97 in a comment above: the answer is no. I'll give a bit more explanation here why the answer is no. Cycling occurs when you start with some basis say $B_0$, and then have a sequence of pivots, resulting in bases $B_1,\dots,B_k$, such that $B_k=B_0$. Note that the entire basis must be repeated, not just a single variable in the basis. Actually, it's very normal in the simplex method for variables to be repeated across pivots, since pivoting in the simplex method only changes one variable in the basis at a time.

Cycling is a problem because if this can happen, then it is possible for the simplex method never to converge to an optimal solution if it gets stuck in this cycle. Fortunately there are simple methods to avoid cycling. One simple method is to simply make sure never to revisit a basis that you've already visited before. Another is Bland's rule.

Fortunately, cycling can only happen when you have degeneracy, in the sense that none of the pivots in the sequence increase the value of the objective function, i.e. by pivoting on columns that have zero reduced cost. This is pretty rare in practical problems but it is possible to construct examples that exhibit this behaviour; see for instance Beale's paper on the topic.