Cycling

Section 2.3 Cycling

In this section, we discuss a potentially serious hurdle to using the Simplex Algorithm, and show how to avoid it completely.

🔗

Activity 2.3.1.

Consider the following canonical maximization tableau:

🔗

$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$- 1$
$- 12.5$	$- 2$	$12.5$	$1$	$0$	$= - t_{1}$
$1$	$0.24$	$- 2$	$- 0.24$	$0$	$= - t_{2}$
$4$	$1.92$	$- 16$	$- 0.96$	$1$	$= f$

🔗

(a)

Perform the following sequence of pivots, ensure each time that it is a valid pivot according to Definition 2.2.6, and keep track of the variables.

🔗

$?$	$?$	$?$	$?$	$- 1$
$- 12.5$	$- 2$	$12.5$	$1$	$0$	$= - ?$
$1^{*}$	$0.24$	$- 2$	$- 0.24$	$0$	$= - ?$
$4$	$1.92$	$- 16$	$- 0.96$	$1$	$= f$

$?$	$?$	$?$	$?$	$- 1$
$?$	$?^{*}$	$?$	$?$	$?$	$= - ?$
$?$	$?$	$?$	$?$	$?$	$= - ?$
$?$	$?$	$?$	$?$	$?$	$= f$

$?$	$?$	$?$	$?$	$- 1$
$?$	$?$	$?$	$?$	$?$	$= - ?$
$?$	$?$	$?^{*}$	$?$	$?$	$= - ?$
$?$	$?$	$?$	$?$	$?$	$= f$

$?$	$?$	$?$	$?$	$- 1$
$?$	$?$	$?$	$?^{*}$	$?$	$= - ?$
$?$	$?$	$?$	$?$	$?$	$= - ?$
$?$	$?$	$?$	$?$	$?$	$= f$

$?$	$?$	$?$	$?$	$- 1$
$?$	$?$	$?$	$?$	$?$	$= - ?$
$?^{*}$	$?$	$?$	$?$	$?$	$= - ?$
$?$	$?$	$?$	$?$	$?$	$= f$

$?$	$?$	$?$	$?$	$- 1$
$?$	$?^{*}$	$?$	$?$	$?$	$= - ?$
$?$	$?$	$?$	$?$	$?$	$= - ?$
$?$	$?$	$?$	$?$	$?$	$= f$

🔗

(b)

Compare your final tableau to the initial tableau. Are there any similarities?

🔗

Activity 2.3.2.

Consider the canonical linear optimization problem: Maximzie

f (x, y) = x + y,

subject to

🔗

\begin{aligned} - 2 x + y & \leq 0 \\ x - 2 y & \leq 0 \\ x + y & \leq 4 \\ x, y & \geq 0. \end{aligned}

🔗

(a)

Consider a sequence of pivots swapping

x \leftrightarrow t_{2},

y \leftrightarrow t_{1}

t_{1} \leftrightarrow y,

t_{2} \leftrightarrow x .

In each of these cases, what is the basic solution recorded by the tableau?

🔗

$The feasible region with multiple lines intersecting the origin.$

🔗

Definition 2.3.3.

If a series of pivots in accordance to Definition 2.2.6 allows one to return to a set of basic variables achieved earlier in the algorithm, we call this phenomena cycling.

🔗

Definition 2.3.4.

If a pivot on a tableau gives a new tableau corresponding to the same basic solution, we call the pivot a degenerate pivot.

🔗

Cycling is bad, since potentially this allows the Simplex Algorithm to not terminate. Fortunately, there is a solution to this issue.

🔗

Theorem 2.3.5. Bland’s Anticycling Rules.

List all variables, independent and dependent in the initial tableau. Then consider the following rules:

🔗

Whenever there is more than one possible choice for a pivot row according to Definition 2.2.6: select the row corresponding to the variable closest to the front of the initial list.
Whenever there is more than one possible choice for a pivot column according to Definition 2.2.6: select the column corresponding to the variable closest to the front of the initial list.

Then the Simplex Algorthm will not cycle.

🔗

Proof.

For the sake of notation, we denote the initial tableau:

$x_{1}$	$x_{2}$	$\dots$	$x_{m}$	$- 1$
$a_{11}$	$a_{12}$	$\dots$	$a_{1 m}$	$b_{1}$	$= - x_{m + 1}$
$a_{21}$	$a_{22}$	$\dots$	$a_{2 m}$	$b_{2}$	$= - x_{m + 2}$
$⋮$	$⋮$	$⋱$	$⋮$	$⋮$	$⋮$
$a_{n 1}$	$a_{n 2}$	$\dots$	$a_{n m}$	$b_{n}$	$= - x_{m + n}$
$c_{1}$	$c_{2}$	$\dots$	$c_{m}$	$d$	$= f$

and order the variables in the associated way. Suppose we follow Bland’s rules and still have cycling. That is, there is a sequence of pivots and bases (set of basic variables)

B_{1} \to B_{2} \to \dots B_{ℓ} \to B_{1} .

We call a variable

x_{j}

fickle if

x_{j}

is in one, but not all of the bases. That is, it leaves a basis, and reenters it later during the cycle.

Note that in order for cycling to occur, each pivot must be degenerate (ask yourself why?). So if

x_{j}

is fickle,

x_{j} = 0

for each basic solution during the cycle.

Since the number of variables is finite, the set of fickle variables is also finite, and let

x_{t}

denote the fickle variable with largest subscript. Suppose that

x_{t} \in B_{i}, x_{t} \notin B_{i + 1}

(why must such a

B_{i}

exist?). Denote the entering variable from

B_{i} \to B_{i + 1}

with

x_{s} .

$\dots$	$x_{s}$	$\dots$	$- 1$
$\dots$	$\dots$	$\dots$	$⋮$
$⋮$	$a_{t s}$	$⋮$	$0$	$= - x_{t}$
$\dots$	$\dots$	$\dots$	$⋮$
$\dots$	$c_{s}$	$\dots$	$d$	$= f$

$\dots$	$x_{t}$	$\dots$	$- 1$
$\dots$	$\dots$	$\dots$	$⋮$
$⋮$	$?$	$⋮$	$0$	$= - x_{s}$
$\dots$	$\dots$	$\dots$	$⋮$
$\dots$	$?$	$\dots$	$d$	$= f$

Note that

x_{s}

must also be fickle (why?) and so

s < t .

We call the dictionary for a basis the system of equations corresponding to that basis. So the dictionary for

B_{i}

D_{i}

which we can write as:

\begin{aligned} x_{k} & = b_{k} - \sum_{x_{j} \notin B_{i}} a_{k j} x_{j} for k \in B_{i} . \\ f & = \sum_{x_{j} \notin B_{i}} c_{j} x_{j} - d . \end{aligned}

Note that since the above pivot was valid, we must have that

c_{s} > 0, a_{t s} > 0

and since the pivot was degenerate, we have

b_{t} = 0 .

Now, because we have cycling, we must have that

x_{t}

reenters the basis at some point

$\dots$	$x_{t}$	$\dots$	$- 1$
$\dots$	$\dots$	$\dots$	$⋮$
$⋮$	$?$	$⋮$	$0$	$= - x_{?}$
$\dots$	$\dots$	$\dots$	$⋮$
$\dots$	$c_{t}^{*}$	$\dots$	$d$	$= f$

$\dots$	$x_{?}$	$\dots$	$- 1$
$\dots$	$\dots$	$\dots$	$⋮$
$⋮$	$?$	$⋮$	$0$	$= - x_{t}$
$\dots$	$\dots$	$\dots$	$⋮$
$\dots$	$?$	$\dots$	$d$	$= f$

Note that for this pivot to be valid, we have that

c_{t}^{*} > 0 .

If we let

D_{ℓ}

denote the dictionary before

x_{t}

re-enters the basis, we have:

f = \sum_{x_{j} \notin B_{ℓ}} c_{j}^{*} x_{j} - d

So note that the solution space to the system of equations for both these dictionaries are the same. So we have a solution for

D_{i}

(not neccessarily feasible ie non-negativity may fail) that must also be a solution to

D_{ℓ} :

\begin{aligned} x_{s} & = Z \\ x_{j} & = 0 for x_{j} \notin B_{i}, x_{j} \neq x_{s} \\ x_{k} & = b_{k} - a_{k s} Z for x_{k} \in B_{i} \\ f & = c_{s} Z - d . \end{aligned}

So we have

c_{s} Z - d = f = c_{s}^{*} Z - d + \sum_{x_{k} \in B_{i}} c_{k}^{*} (b_{k} - a_{k s} Z)

where

c_{k}^{*} = 0

for

x_{k} \in B_{ℓ} .

So via algebra:

(c_{s} - c_{s}^{*} + \sum_{x_{k} \in B_{i}} c_{k}^{*} a_{k s}) Z = \sum_{x_{k} \in B_{i}} c_{k}^{*} b_{k} .

The above equation holds true no matter what

Z

is. Thus:

c_{s} - c_{s}^{*} + \sum_{x_{k} \in B_{i}} c_{k}^{*} a_{k s} = 0.

Note that

x_{t},

NOT

x_{s}

is entering the basis. If

x_{s}

is already in the basis,

c_{s}^{*} = 0 .

Otherwise,

c_{s}^{*} \leq 0,

otherwise

s

would have entered by Bland’s Anticyling rules. We’ve also shown

c_{s} > 0 .

Thus

\sum_{x_{k} \in B_{i}} c_{k}^{*} a_{k s} < 0

which is only possible if there is some

x_{r} \in B_{i}

such that

c_{r}^{*} a_{r s} < 0.

From this, we know that

c_{r}^{*} \neq 0 .

x_{r} \notin B_{ℓ},

but

x_{r} \in B_{i},

x_{r}

is fickle. Since

t

is the largest index of a fickle variable,

r < t .

Note that

x_{r}

is not entering from

B_{ℓ},

c_{r}^{*} \leq 0 .

Thus

a_{r s} > 0 .

But

x_{r}

is fickle, so

b_{r} = 0

D_{i} .

But then, we would have picked

x_{r},

not

x_{t}

to leave.

$\dots$	$x_{s}$	$\dots$	$- 1$
$\dots$	$\dots$	$\dots$	$⋮$
$⋮$	$a_{t s}$	$⋮$	$0$	$= - x_{t}$
$⋮$	$a_{r s}$	$⋮$	$0$	$= - x_{r}$
$\dots$	$\dots$	$\dots$	$⋮$
$\dots$	$c_{s}$	$\dots$	$d$	$= f$

which is a contradiction.

Activity 2.3.6.

If we follow Theorem 2.3.5 then no basis is visited twice during the Simplex Algorithm. Note that

f

is non-decreasing with each pivot. Must the Simplex Algorithm terminate? Why?

🔗