6
$\begingroup$

I'm reading Schrijver's Theory of Linear and Integer Programming, and I have a problem understanding cycling happens in the simplex method. The simplex is described as below:

Solving $\max\{cx\mid x \geq 0; Ax \leq b\}$ At each stage a set $C_k$ is maintained, which consists of $n$ linearly independent equalities from $Ax = b$, such that $x_k$ the current vertex is determined by $C_kx_k = b_C$.

$u$ is the unique vector $u_kA = c$ where $u$ is zero in the components corresponding to equalities outside $C_k$. if $u \geq 0$ then $x_k$ is optimal. Otherwise we choose an index $i^*$ where $u_{i^*} <0$, $y$ is the unique vector such that $C_ky$ is zero in all components except $i^*$. Then $\lambda$ is defined as $\min\{\frac {b_t - (Ax_k)_t}{(Ay)_t}, (Ay)_t > 0\}$, where $t^*$ is the index acquiring the minimum. Now $x_{k+1}$ is calculated from $x_k + \lambda y$ and $C_{k+1} = C_k + t^* \setminus i^* $. Also notice $cy = uAy = -u_{i^*} > 0$ so $cx_{k+1} > cx_k$.

So the book explains when choosing $i^*$ and $t^*$ and there are several options, there are different methods for breaking ties, some of which may cause cycling that is the algorithm wouldn't terminate. Here is what I don't understand: given there are finitely many vertices and $cx_{k+1} > cx_k$ how is it possible to visit the same vertex twice hence encountering cycling??

Later, when the average time of Simplex method is being analyzed due to Borgwardt, the book explains cycling can happen only if the LP problem is degenerate. And provides a condition for being non-degenerate there is no set of $n$ linearly dependent rows in the matrix $\begin{bmatrix}c\\A\end{bmatrix}$ and there is no set of $n+1$ linearly dependent rows in $\begin{bmatrix}A &b\end{bmatrix}$. can you please explain why is this?

$\endgroup$
3
$\begingroup$

Cycling happens in a different scenario: when $cx_{k+1} = cx_k$. This happens when the current solution is degenerate, that is, when the set $C_k$ is not unique.

For a worked out example, see Cycling in linear programming problems or The simplest examples where the simplex method cycles and conditions where EXPAND fails to prevent cycling. There are many other resources which are available online.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.