The simplest examples where the simplex method cycles and conditions where expand fails to prevent cycling.
This paper introduces a class of linear programming examples that cause the simplex method to cycle and that are the simplest possible examples showing this behaviour. The structure of examples from this class repeats after two iterations. Cycling is shown to occur for both the most negative reduced cost and steepest-edge column selection criteria. In addition it is shown that the expand anti-cycling procedure of Gill et al. is not guaranteed to prevent cycling.
Introduction
Degeneracy in linear programming is of both theoretical and practical impor-
tance. It occurs whenever one or more of the basic variables is at its bound,
and when this occurs it is possible that an iteration of the simplex method
fails to improve the objective function. The simple proof of finiteness of the
simplex algorithm relies on a strict improvement in the objective function
at each iteration and the fact that the simplex method visits only basic solu-
tions, of which there are a finite number. However if the problem is degenerate
this proof does not hold: there is the possibility of a consecutive sequence of
iterations occurring with no change in the objective function and with the
eventual return to a previously encountered basis. Examples, such as Beale's
well known example [2], have been constructed to show that this can happen,
supported by EPSRC grant GR/J0842
Preprint submitted to Elsevier Preprint 29 September 1996
though such examples do seem to be very rare in practice. A more common
practical situation is where a long but finite sequence of iterations occurs without
the objective function improving - a situation called stalling - and this
can degrade the algorithm's performance.
A related issue is the behaviour of the simplex algorithm in the presence of
roundoff error. At a degenerate vertex there is a serious danger of selecting
pivots which are small and have a high relative error.
A wide range of methods have been suggested to avoid these problems.
Lexicographic ordering: These methods are guaranteed to terminate in exact
arithmetic but are often prohibitively expensive to implement for the revised
simplex method and do not address the problem of inexact arithmetic.
Primal-dual alternation methods: These methods were introduced by Balin-
ski and Gomory [1] and have recently been developed by Fletcher [3,5,4].
Some of these methods both guarantee to terminate in exact arithmetic and
exhibit good behaviour with inexact arithmetic.
Constraint perturbation methods and feasible set enlargement methods:
These method attempt to reduce the likelyhood of cycling and also attempt
to improve the numerical behaviour and reduce the number of iterations.
The Devex and expand procedures described below are of this type. In addition
it is claimed that stalling cannot occur with expand. Wolfe's method
is a recursive perturbation method which guarantees termination in exact
arithmetic.
In [10] Wolfe introduced a perturbation method which is guaranteed to terminate
in a finite number of steps in exact arithmetic. In this method whenever
a degenerate vertex is encountered, the bounds producing the degeneracy are
expanded in such a way that the current vertex is no longer degenerate. Other
bounds on the basic variables are temporarily ignored. The simplex method
works on this modified problem until an unbounded direction is found. If the
bound expansion is random, it is highly unlikely that further degenerate vertices
will be encountered before the unbounded direction is found. However if
a further degenerate vertex is discovered, it is guaranteed to have fewer active
constraints. The perturbation process is repeated and since it is guaranteed
that each successive degenerate vertex has fewer active constraints, after a
finite number of steps a non-degenerate vertex is reached with an unbounded
direction. This direction is then used in the original problem to give an edge
leading out of the degenerate vertex. It is not obvious how to extend this
method to the case of inexact arithmetic as there is then no obvious criterion
for what constitutes a degenerate vertex.
In [9] Harris introduced the Devex row selection method, which allowed small
violations of the constraints and used this flexibility to choose the largest pivot.
This has the advantage of both avoiding small pivots and reducing the number
of iterations. The disadvantage is that the constraints are violated and some
steps are in the negative direction. The variable leaving the basis does not
normally do so at one of its bounds, but is shifted to that value, resulting in
inconsistent values for the basic variables. An attempt is made to correct this
inconsistency at regular intervals (usually after each reinversion) by doing a
reset, in which the basic variable values are recalculated from the values of the
nonbasic variables. This can produce infeasible values for the basic variables
(i.e. outside the specified tolerance) so there is no guarantee that progress has
been made. However the method seems to be effective in practice in reducing
the number of iterations taken, and variants of it are used in some commercial
codes.
Gill et al [7] developed the expand method in an attempt to improve on the
good features of the Devex method of Harris and also to incorporate some features
of Wolfe's method which guarantee finite termination. The performance
of minos was significantly improved by the incorporation of expand. At each
iteration of the expand method the bounds are expanded by a small amount.
As in Devex, the largest pivot which does not lead to any constraint violation
(beyond the current expanded position) is chosen. If the normal step for the
largest pivot is sufficiently positive, it is taken, otherwise a small positive step
is taken. In all cases the variable values stay within their expanded bounds.
Because at every iteration the nonbasic variable is moved a positive amount
in the direction which improves the objective function, it can never return to
a previous value.
In this paper we shall introduce and analyse the simplest possible class of
cycling examples, the 2/6-cycle class. In Section 2 we present an example of
the class which cycles when using the most negative reduced cost column selection
criterion. In Section 3 the general form of such examples is derived. In
Section 4 a variation of the example is introduced which cycles for the steepest
edge column selection rule. In Section 5 the behaviour of the expand procedure
is analysed and a simple necessary and sufficient condition is derived for
indefinite cycling to occur when using expand.
example
We shall first solve the four variable, two constraint problem (1) by the simplex
method. The analysis later in the paper will show how to derive examples of
this form. This problem is unbounded. A bounded example with identical
behaviour can be obtained by adding the upper bound constraints x
and x 2 - 1, either as implicit upper bounds or with one or more explicit
constraints. The variable to enter the basis will be chosen by the most negative
reduced cost criterion and, where there is a tie for the variable to leave the
basis, the variable in the row with the largest pivot will be chosen.
subject to 0:4x 1
After introducing slack variables x 5 and x 6 and writing the equations in detached
coefficient form we get tableau T (1) . All the variables are initially zero
and will remain zero at every iteration. In the first iteration x 1 is chosen to
enter the basis. There is only one positive entry in the x 1 column, so there is a
unique pivot choice with x 5 leaving the basis. Making this basis change leads
to tableau T (2) . In the second iteration x 2 is chosen to enter the basis. In the
normal ratio test there is a tie between x 6 and x 1 to leave the basis. Breaking
the tie by using the larger pivot (as is normal for numerical stability) gives x 6
to leave the basis, and making this basis change yields tableau T (3) .
-2.3 -2.15 13.55 0.4
2.5 -19.5 -3.5 19.5
-2.3 -2.15 13.55 0.4
Note that tableau T (3) is the same as tableau T (1) with the x variable columns
shifted cyclically two columns to the right. It follows that this example will
return to tableau T (1) after a further 4 iterations and therefore will cycle
indefinitely. In this example there are only two sets of coefficients: T (3) and
T (5) are the same as T (1) with the x variable columns shifted cyclically 2 and
4 columns to the right, and T (4) and T (6) are the same as T (2) again shifted
cyclically 2 and 4 columns to the right. We shall refer to such examples as 2/6-
cycle examples. In this paper we shall restrict attention to 2/6-cycle examples
as they are more elegant and easier to analyse than 6/6-cycle examples, such
as Beale's example, which take 6 iterations to repeat the same coefficients.
All the results here are demonstrated for 2/6-cycle examples, however this
property is not needed for the results and indeed 6/6-cycle examples can be
formed by perturbing the 2/6-cycle examples given in this paper.
3 The form of 2/6-cycle examples
The following analysis was used to construct the above example. Partition the
3 \Theta 6 matrix M (1) formed from the x columns of T (1) as follows
a b 07 5
and I are 2 \Theta 2 blocks of the constraint rows and a, b and 0 are
blocks of the objective row. To be able to pivot on the (1,1) and (2,2)
entries in iterations 1 and 2, we require A to be non-singular. These pivoting
operations yield tableau T (3) whose submatrix formed from the x columns has
the form
For the constraint pattern to repeat after these two iterations we require
occurs if and only if A This implies that the
eigenvalues, -, of A satisfy
0: (2)
For a 2 \Theta 2 real matrix A there must either be 2 real eigenvalues or a complex
conjugate pair.
It follows from (2) that if A has real eigenvalues they must both have the value
1, in which case the 2 \Theta 2 matrix polynomial A 2 +A+I has two real eigenvalues
of 3 and is therefore non-singular. Since
follows that A = I in this case. It is then easy to show that a
is of no interest as it corresponds to a zero cost row.
The other possibility is that A has a complex conjugate pair of eigenvalues,
and it follows from (2) that they must satisfy
The characteristic equation of a general 2 \Theta 2 matrix A is
Equations (3) and (4) hold for the two distinct values of -, so it follows that for
a suitable 2/6-cycle example we require A 11 +A
1. From these it follows that
Conversely any 2 \Theta 2 matrix such that A 11 +A holds has characteristic
equation (3). Since a matrix satisfies its own characteristic equation,
0, from which it follows that A
The objective function will repeat after 2 iterations if and only if b\GammaaA
This occurs if and only if 0, and this holds
for all a since A 2 +A+ I = 0. There is therefore no restriction on a. Since the
scaling of the objective row is arbitrary we shall take a to have the form
where there is no restriction on the value of -. It follows that there is a three
parameter family of 2/6-cycle examples: the parameters can be chosen as -,
A 11 and A 12 .
For arbitrary a, the vector b must satisfy
Since A is real and A
and it follows that the general form of M (1) and M (2) for the 2/6-cycle examples
with the pivot sequence fixed is as in Table 1.
Proposition 1 summarises these results.
Proposition 1 Assume the cost row is nonzero and the 2/6-cycle pattern of
pivots is selected, then the necessary and sufficient conditions for the coefficient
pattern to repeat after two iterations are that the coefficients have the form
given in tableau M (1) of Table 1, and that A 11 , A 21 and A 12 satisfy (5).
We shall now deduce the inequality relations which must be satisfied for the
simplex method to select (1,1) and (2,2) as pivot elements. In order for (1,1)
to be a pivot in tableau M (1) we require

Table
Coefficient values over two iterations for 2/6-cycle examples
A 11 A 12
A 11
A 11
A 11A 11
A 11
A 11
A 11
A 11
A 11
A 11
A 11
From (5) and (7) it follows that A 21 and A 12 are nonzero and have opposite
signs. If A 21 is positive, A 12 and hence A 12
A 11
are negative, so entry M (2)
12 is
negative and M (2)
22 is positive, which is just the situation in the numerical
example shifted cyclically one column to the right and with rows 1 and 2
interchanged. Hence without loss of generality we can take
It follows that the first row has the only positive entry in column 1 of M (1) and
both constraint row entries in column 2 of M (2) are positive. Hence row 1 is the
unique pivot candidate in iteration 1. There are two possible choices of pivot
in column 2 of iteration 2. We shall use the largest pivot rule which breaks a
tie by choosing the largest possible pivot, which would normally be the choice
from the point of view of numerical stability. To simplify the presentation we
shall assume that if there still remains a tie after applying this rule, then the
pivot in row 1 is chosen. This second tie break rule therefore breaks the 2/6-
cycle pattern if the pivot size criterion does not determine the pivot row. It
follows that row 2 is the pivot choice in column 2 of iteration 2 if and only ifA 11
A 11
We have therefore proved the following proposition.
Proposition 2 If the conditions of Proposition 1 are met and row selection
ties are resolved by choosing the largest pivot and the columns are selected in
the 2/6-cycle order, then the necessary and sufficient conditions for row 1 to
be selected in odd iterations and row 2 in even iterations are 0 ! A 11 and
The conditions which guarantee that column 1 is chosen in M (1) by the most
negative reduced cost rule rather than column 2 or 3 are
A 21
It follows from (7) and (8) that - is negative. Column 1 is guaranteed to be
chosen rather than column 4 if and only if
A 11
which is always true as this bound is positive by (7) and (10).
In M (2) column 5 has a positive cost entry so is not a candidate. The necessary
and sufficient conditions for column 2 to be a candidate and be guaranteed to
be chosen rather that columns 3 or 4 are
A 11
A 11
A 11
Comparing (13) and (15) we see that (13) is redundant if
A 11
which is true by (9). Comparing (14) and (15), then using (8) and then (5),
we see that (14) is redundant if
A 11
A 11
A 11
which shows is true. Comparing (12) and (13), then using (8) and then
(5), we see that (12) is redundant if
A 11
A 11
A 21
which (7) shows is true.
We have now shown that (12), (13) and (14) are redundant so (15) is always
the tightest upper bound. From this and (11) it follows that - must lie in the
range
A 11
and there is a positive gap between these bounds if and only if
A 11
If the left hand inequality in (16) is reversed, then column 2 will be chosen
rather than column 1 in M (1) , and if the right hand inequality is reversed, then
column 4 will be chosen instead of column 2 in M (2) . In either case the 2=6-
cycle pattern will be broken. If either inequality in (16) holds as an equality,
then the most negative reduced cost rule does not uniquely determine the
column to enter the basis. To simplify presentation we will assume that when
this occurs a choice is made which breaks the 2=6-cycle pattern.
We have now shown
Proposition 3 Assume that the the most negative reduced cost column selection
rule and the largest pivot row degeneracy tie breaking rule are used, then a
4 variable 2 constraint degenerate LP problem will have the 2/6-cycle pattern
and cycle indefinitely if and only if the conditions of Propositions 1 and 2 hold
and in addition (16) holds (which implies (17)).
The unshaded area in Figure 1 (ignoring the dashed constraint) shows the
region where the problem cycles indefinitely. Taking A
then scaling the objective row by 2:3, produces the
example given in Section 2.
A similar analysis to that leading to Proposition 1 for the case of a 2=4-cycle
example shows that the cost row must be zero, so such examples cannot cycle.
It is also straightforward to show that there can be no cycling examples with
all pivots in the same constraint row, so there can be no problems with a
single constraint. In the 2=6-cycle examples A 12 and A 21 must have different
signs, so it follows from Table 1 that the even and odd iterations cannot be
the same. It therefore follows that the 2=6-cycle examples are the simplest
possible cycling examples.
A 120.0
A 11
< A 11
A
Fig. 1. Cycling region is unshaded. (Also cycles for expand if A 11 - 1
4 A cycling steepest edge example
In the previous sections the column was selected using the original Dantzig
criterion of most negative reduced cost. In the steepest edge method [8] the
column is selected on the basis of the most negative ratio of the reduced cost
to the length of the vector corresponding to a unit change in the nonbasic
variable. This normally leads to a significant reduction in the number of itera-
tions. When steepest edge column selection is used on the example in Section
2, column 2 is chosen in T (1) instead of column 1 and in the following iteration
the problem is shown to be unbounded so the simplex method terminates in
iterations. However by adding an extra row, which affects the steepest edge
weights but not the choice of pivot row, a steepest edge cycling example can
be constructed.
To preserve the 2/6-cycle pattern of the example, any extra constraints must
behave like the objective row in that they must satisfy (6). We shall now
construct an example which has a single candidate column in column 2 of
T (2) . We do this by selecting - so that the x 4 objective coefficient in T (2) is
zero. It follows from Table 1 that the required value of - is
this results in the tableaux shown in Table 2, omitting the third rows. Note
that column 1 would not now be selected in T (1) either by the most negative
reduced cost criterion or by the steepest edge criterion. We now introduce
a constraint which will leave the steepest edge weight of column 1 of T (1)
unaltered but increase the weight of column 2. If the entries in this constraint

Table
Cycling example with steepest edge column selection
2.5 -19.5 -3.5 19.5
are scaled up sufficiently, we can make steepest edge choose column 1. Using
applying (6) we get the third row of tableau T (1) . We set
the right hand side of this constraint to 1 and this ensures that this constraint
is not involved in any of the pivot choices even when the matrix coefficients
are perturbed by a small amount. With this extra row added the steepest edge
reduced costs for columns 1 and 2 of T (1) are -0.127 and -0.087, which leads
to the selection of column 1 as required.
5 Analysis of the expand procedure
The analysis given by Gill et al [7] of their expand procedure proves that the
objective function can never return to a value it had at a previous iteration.
The expand procedure however relaxes the constraints at each iteration, so
the fact that the objective function continually improves does not prove that
the method will not return to a previous basic solution. If this could occur
the method might cycle. In section 5.1 we describe the expand procedure and
in section 5.2 derive the necessary and sufficient condition for cycling still to
occur with the 2/6-cycle examples when using expand. We do this by deriving
an expression for the values of every variable at every iteration, a task that is
made tractable by the special structure of the 2=6-cycle examples.
5.1 The expand ratio test
The expand approach to resolving degeneracy is described by Gill et al in [7]
for the general bounded LP problem. The examples in this paper have single
sided bounds and are of the form
subject to
so for simplicity, expand is discussed here for this problem Assuming that
all the variables are feasible (x - 0), the standard ratio test for the simplex
method determines the maximum step ff in the direction p corresponding to
the pivotal column such that the variables remain feasible, that is x
For each i, the step which zeroes x i is ff
The maximum feasible step is therefore and the variable to
leave the basis is x r .
expand is based on the use of an increasing primal feasibility tolerance ffi.
During a particular 'current' simplex iteration, this tolerance has the value
was the value of ffi in the previous iteration. At the beginning
of the current iteration each variable satisfies its expanded bound x i
it is always possible to ensure that ff ? 0 so there is a strict
decrease in the objective function.
The expand ratio test makes two passes through the entries in the pivotal
column p.
- The first pass determines the maximum acceptable step ff max ? 0 so that
each basic variable satisfies its new expanded bound x i - \Gammaffi .
- The second pass determines a variable x r to leave the basis. x r is the variable
with the largest acceptable pivot and is defined by
. This is the step necessary to zero x r . Note that if x r
full will be negative.
- A minimum acceptable step
is calculated. If x
ffi then this is the maximum step which can be taken
whilst maintaining feasibility with respect to the new expanded bounds.
- The actual step returned by the expand ratio test is
full
We shall refer to these two alternative step sizes as the min and the full
step.
The initial values of the nonbasic variables are zero. In the 2/6-cycle examples
the initial values of the basic variables are also zero. The initial value of the
expanding feasibility tolerance will be denoted by -u, where u - 0, and the
tolerance during iteration n will be denoted by -u n . It follows that u
5.2 Conditions under which cycling occurs with the expand ratio test
We shall now analyse the behaviour of the 2=6-cycle problems when using
the expand ratio test and derive necessary and sufficient conditions for the
2=6-cycle problems to cycle indefinitely.
The action of the expand ratio test depends on whether the iteration number
is even or odd, so we shall consider separately the behaviour in iterations
We shall now assume that the pivot columns
are selected in the 2/6-cycle order and derive the necessary and sufficient
conditions for expand to select a pivot in the first row in odd iterations and
have a unique pivot in the second row in even iterations. We shall also show
that the min step is taken when the pivot is in row 1 and the full step is taken
when the pivot is in row 2.
Let x n
i denote the value of x i at the start of iteration n. The subscripts of x
will be calculated modulo 6.
For iteration the pivotal column is [ A 11 A 21 ] T and the values of the
basic variables at the start of the iteration are respectively x 2k+1
2k .
Since A towards its bound so it is the
sole candidate to leave the basis. The second pass of the expand ratio test
returns
A 11
and if
the min step will be taken so
A 11
It follows that if (18) holds the changes in variable values are as given in row
1 of

Table

3.
For iteration 2k the pivotal column is [ A 12 =A 11 1=A 11 ] T and the values
of the basic variables at the start of the iteration are respectively x 2k+2
2k+1 and
x 2k+2
2k . Since A 11 ? 0 and A 12 ? 0, both variables move towards their bound.
The first pass of the expand ratio test returns
x 2k+2
A 12 =A 11
x 2k+2
1=A 11
A sufficient condition for the pivot to be in row 2 is that A 12 ! 1 and that
the pivot is acceptable. It is acceptable if and only if
x 2k+2
1=A 11
x 2k+2
A 12
so the pivot in row 2 is acceptable if and only
if
A 12 x 2k+2
Also provided that
x 2k+2
then ff full = A 11 x 2k+2
so the full step, ff full , is taken and the
expand ratio test returns
Hence if (19) and (20) hold, then the changes in values are as given in row 2
of

Table

3.
Using the changes in the values of variables given in Table 3, the expressions in

Table

4 for the values of each variable over any two iterations are established by
induction. To simplify notation we introduce the quantities s k and S k defined
by
0:
Note that since A 11 ? 0, s k and S k are nonnegative. Also

Table

3.
Changes
in
values
of
variables
over
two
iterations
Entering
Leaving
Remaining
Step
x
x
x
x
x
x
Pivot
row
1.
Min
step
x
x
x
x
x
Pivot
row
2.
Full
step

Table

4.
Expressions
for
the
values
of
each
variable
over
any
two
iterations.
s
A
i)A
in
x
x
x
x
x
x
Expanded
Normal
\Gamma-S
\Gamma-A21s
\Gamma(A11
\GammaA120
\Gamma(A11
-(
)\Gamma-S
\Gamma-
s
\Gamma(1+
-(
\Gamma(1+
s
s
\Gamma-A21s
\Gamma-S
The expressions in Table 4 allow condition (19) to be expressed as G k - 0,
where G k for k - 0 is defined by
A 11
A 11
A necessary and sufficient condition on A 11 for G k - 0 is established by
considering
A 11
A k+1
2:
It follows that \DeltaG k - 0 () s k+2 - 2. If
to a limit s 1 , where s 1 - 2. In this case \DeltaG k - 0 for all k so G k+1 - G k for
all k, and also G 0 -
, then there
exists an ffl and K such that s k+2 It follows that for
suitably large k, G k ! 0. Hence for positive A 11 the necessary and sufficient
conditions for G k to be nonnegative for all k is that A 11 - 1
.
Proposition 4 Assume that the conditions of Proposition 1 are met and the
expand row selection method is used and the columns are selected in the 2/6-
cycle order. Then necessary and sufficient conditions for cycling to occur are
that
Proof:
Sufficient conditions:
We shall show by induction that the values of the variables at the start of odd
iterations are as given in Table 4 and that these values lead to the correct
choice of pivot row for the 2/6-cycle pattern.
Initially all the variables have the value zero so x 1
Hence the values in

Table

4 are correct for Assume now that for some k the values in Table
4 are correct at the start of iteration 2k + 1.
In iteration 2k + 1, since s k is non-negative, x 2k
holds and it
follows that the changes in the values of variables are as given by row 1 of

Table

1. From this and (21) we get
x 2k+2
A 21
A 11
\Gamma- A 21
A 11
\Gamma- A 21
A 11
All the other values are straightforward so we have deduced the values given
in

Table

4 at the start of iteration 2k 2.
Substituting these values into (19) we see that the pivot in row 2 is acceptable
if and only if
A 11
A 11
which is true provided A 11 - 1
2 . Also
x 2k+2
A 11
A 11
since A 11 ? 0 (7) and A 12 ! 1. Hence (20) holds, so the changes in the values
of variables are as given in row 2 of Table 3. The new value for x 2k+1 is given
by
x 2k+3
A 11
A 11
A 11
A 11
A 11
A 11
which is the value given in Table 4. All the other values at the start of iteration
straightforwardly and are as shown in Table 4. These values are
the values in Table 4 for k, with the k replaced by k + 1. This completes the
induction and shows that the 2/6-cycle pattern continues indefinitely.
Necessary conditions:
As discussed in Section 3, A 11 ? 0 and we can choose A 12 ? 0, in which case
the first iteration takes the min step and so x 2
The pivot in row 1 in iteration 2 is acceptable if
A 11
A 11
A 12
A 12
A 11
A 11
which is true. Hence if A 12 ? 1, the pivot will be in row 1 in iteration 2 and
the 2/6-cycle pattern will be broken. If A 11 ? 1, then the argument prior to
Proposition 4 shows there is a first value of k, -
K say, such that G -
As shown above for all
K the 2/6-cycle pattern is maintained and the
variable values are as in Table 4. In iteration 2 -
K therefore the pivot in row
2 is not acceptable so the pivot must be in row 1. This breaks the 2/6-cycle
pattern. 2
The conditions derived in Section 3 for the minimum reduced cost criterion to
choose pivot columns in the 2/6-cycle pattern relied on the conditions A 11 ? 0
These conditions have been established in Proposition 4 for
the case of expand row selection, so it follows that (16) and (17) still hold.
From (17) and the fact that A 11 - 1
it follows that A 12 ! 3
which is tighter
that A 12 ! 1, which is therefore redundant. We have now shown the following
proposition
Proposition 5 A 4 variable 2 constraint degenerate LP problem will have the
2/6-cycle pattern and cycle indefinitely when using the most negative reduced
cost column selection rule and the expand row selection rule if and only if
the conditions of Proposition 1 hold and in addition
and (16) holds (which implies relation (17)).
The shaded area in Figure 1 now including the A 11 - 1
2 constraint is now the
region where cycling occurs when using expand. Note that now the constraint
redundant. Also note that in the example (1), A
that example also cycles when using expand.
Finally note that the only way that expand can escape from the 2=6-cycle
pattern is for it to select the first row as pivot row in an even iteration, and if
this occurs the resulting tableau has the form
A 11
A 11
A 12
A 12
A 11
A 12
A 11 A 12
A 11
A 11 A
A 12The constraint entries in the third and fourth columns are all negative and
the objective function coefficients in all except these columns are nonnegative.
Hence since the problem is unbounded we cannot be at the optimal so one
of these columns must be chosen with the result that the next iteration will
produce an unbounded step and the method will terminate.
The above results are independent of the expand parameters u and - . In [7]
it is suggested that the initial tolerance -u is taken to be half of the feasibility
tolerance ffi f to which the problem is to be solved. The value of - is chosen so
that after a large number of iterations (typically the expanded
tolerance approaches ffi f , at which stage ffi is reset to its original value ffi i . If this
is done with the 2/6-cycle examples after an even iteration, then the problem
returns to its initial state. If it is done after an odd iteration then it returns
to the even iteration case but with the values all zero. It can be shown that in
this case too the problem cycles, so that in neither case does resetting break
the cycle pattern.
6 Conclusions
We have derived a three parameter class of linear programming examples
which cause the simplex method to cycle indefinitely. When written in standard
form, these examples have two constraints and 6 variables and the co-efficient
pattern repeats every two iterations. These are the simplest possible
examples for which the simplex algorithm cycles. We have derived 4 inequalities
between the parameters and shown that these are the necessary and
sufficient conditions for members of this class to cycle with Dantzig's form of
the simplex. We have shown how to extend the examples so that they also
cycle when the steepest edge column selection criterion is used. By adding
the single bound, A 11 - 1, we were able to characterise the examples which
also cycle using the expand row selection mechanism This shows that despite
the fact that in the expand method the objective function is guaranteed to
improve each iteration, the method is not guaranteed to prevent cycling. The
cycling behaviour is independent of the expand tolerance parameters. The
bound A 11 - 1
2 is the only extra condition that had to be applied to ensure
that an example which would cycle under the usual Dantzig rule with largest
pivot as the tie-breaker, would also cycle using expand. This extra bound
does reduce somewhat the number of cases which cycle but does not eliminate
the problem. This improvement has also to be set against the fact that
expand can cycle when the degeneracy is not exact.
All the coefficients in the examples (not just the 3 parameters) may be perturbed
simultaneously by any small amount without destroying the cycling
behaviour. The 2/6-cycle examples are therefore just points in a full dimensional
set of counter-examples, so there is a positive probability of encountering
cycling in randomly generated degenerate examples. In practice therefore the
expand procedure cannot be relied upon to prevent cycling. Provided we
stay within the class of the degenerate problems (i.e. keep the right hand side
it is possible to vary the other coefficients by a significant amount. Indeed
we have constructed examples where the values are totally different every 2
iterations and yet indefinite cycling still occurs with expand.
The examples have been tested on our own implementation of expand and
using minos5.4, which was written by the authors of expand. In both cases
if no preprocessing is done the examples cycle indefinitely. minos periodically
does a reset operation (by default after 10000 iterations). This returns the
problem to its initial state so cycling is still indefinite.
osl [6] uses some techniques from expand. In the examples in this paper
osl 2.1 without scaling or preprocessing cycles for introducing
a large perturbation, which resolves the degeneracy. cplex 4.0.7
without scaling or preprocessing cycles for 400 iterations before resolving the
degeneracy by introducing a large perturbation. xpressmp 7.14 without scaling
and with an even invert frequency cycles indefinitely. However the robust
bqpd code of Fletcher [4] detects degeneracy at the start of the first iteration,
changes to the dual, then does one pivot in the dual after which it finds that
the dual is infeasible. This gives an improving direction in the primal, which
resolves the degeneracy. Finally bqpd detect unboundedness in this direction
and terminates having done one pivot in total.



--R

A mutual primal-dual simplex method
Cycling in the dual simplex algorithm.
Degeneracy in the presence of roundoff errors.
Resolving degeneracy in quadratic programming.
Towards reliable linear programming.
Implementing the simplex method for the optimization subroutine library.
A practical anti- cycling procedure for linearly constrained optimization
A practical steepest-edge simplex algorithm
Pivot selection methods of the Devex LP code.
A technique for resolving degeneracy in linear programming.
--TR

--CTR
Julian Hall , Ken McKinnon, COAP 2005 Best Paper Award, Computational Optimization and Applications, v.35 n.2, p.131-133, October   2006
Peter Zrnig, Systematic construction of examples for cycling in the simplex method, Computers and Operations Research, v.33 n.8, p.2247-2262, August 2006
degeneracy;simplex method;expand;cycling