Available online at www.sciencedirect.

com

Computers & Operations Research 31 (2004) 303 311

www.elsevier.com/locate/dsw

Note
Cycling in linear programming problems
Saul I. Gassa; , Sasirekha Vinjamurib
a
Robert H. Smith School of Business, University of Maryland, College Park, MD 20742, USA
b
Department of Mathematics, University of Maryland, College Park, MD 20742, USA
Received 1 August 2002; accepted 1 November 2002

Abstract

We collected and analyzed a number of linear programming problems that have been shown to cycle (not
converge) when solved by Dantzigs original simplex algorithm. For these problems, we were interested in
whether or not some of the more popular linear programming solvers would 4nd an optimal solution. This
technical note reviews the results of our analysis and some related topics on cycling.

Scope and purpose

Veri4cation of algorithmic based software can often be a di6cult matter as test problems for checking
anomalous situations are often di6cult to construct. For linear programming software, one such situation that
has to be guarded against is the nonconvergence of a problem, given that it has a 4nite or in4nite optimal
solution. Here we present 11 linear-programming problems that have been shown to cycle when solved by
the original algorithmic rules of the simplex method. All of these problems converged to the proper optimal
solution when solved by three popular simplex solvers. For those interested in constructing other problems
that cycle, we also present necessary conditions that must hold with respect to the problems dimensions.
? 2003 Elsevier Ltd. All rights reserved.

Keywords: Linear programming; Cycling; Degeneracy

1. Introduction

The original proof that the simplex algorithm would converge to an optimal solution invoked the
famous non-degeneracy assumption (NDA) (Dantzig [1]). That is, given that the linear-programming
(LP) problem in question has feasible solutions, then every basic feasible solution has all of its

Corresponding author. Tel.: +1-301-405-2208; fax: +1-301-405-8655.
E-mail address: [email protected] (S.I. Gass).

0305-0548/04/$ - see front matter ? 2003 Elsevier Ltd. All rights reserved.
doi:10.1016/S0305-0548(02)00226-5
304 S.I. Gass, S. Vinjamuri / Computers & Operations Research 31 (2004) 303 311

basic variables strictly positive. For such a problem, Dantzigs prescription for the simplex algorithm
was guaranteed to converge to an optimal solution or show that the optimum was unbounded. (The
reader is referred to [1] or Gass [2] for a description of the simplex algorithm.) If a problem does
not satisfy the NDA (and it is di6cult to discern this prior to solving a problem), then there is
the possibility that the simplex algorithm would not converge to the optimal solution, that is, it
would cycle. Here to cycle means that the simplex algorithm would keep repeating a degenerate
basic feasible solution. If the repeated basis happened to be the optimal one, the simplex method
would not so indicate. Problems that did not satisfy the NDA were easy to construct, but to 4nd
one that did not converge took some eHort. The 4rst instance of a linear-programming problem that
was shown to cycle is the one constructed by HoHman [3]. This problem, which is discussed below,
is an unusual one in that its coe6cients are given in terms of trigonometric functions. HoHman
in his article (and when asked in person) does not : : : recall any considerations that led to the
construction of the example : : : [3]. We note that a feasible basis that has a single degeneracy
cannot cause a cycle and, thus, the NDA can be weakened to allow for single degenerate basic
feasible solutions.
In discussing the simplex algorithm and cycling, we need to diHerentiate between classical cycling
and computer cycling (Gass [4]). Classical cycling arises when the data of the problem are given
in decimal notation and can be expressed as rational fractions. Computations are performed without
loss of accuracy or round-oH error; that is, the data are always transformed from rational fractions to
rational fractions. A standard version of the primal simplex algorithm is used in which the decision
rules for selecting a variable to enter or leave the basis are based on Dantzigs original formulation,
e.g., when ties exist, select the variable (to enter or leave) that has the smallest index. Computer
cycling is an application of the simplex method that does not preserve rational transformations and
uses experiential based criteria for selecting entering or leaving variables, tolerance values for what is
a zero, scaling, and numerical stability procedures. A problem written on paper and solved by hand
(classical mode) is not the same problem entered into a computer and solved by a computer-based
simplex algorithm (computer mode). (A similar discussion can be applied to the dual simplex method
and for the special case of a transportation problem. See Beale [5] for a problem that cycles under
dual simplex rules for selecting the outgoing and incoming variables, and Gassner [6] for examples
of cycling in the transportation and assignment problems.)
It should be clear that if a problem exhibits classical cycling, the chances are that it will not
exhibit computer cycling, and, vice-versa. In the early days of linear programming, there was con-
cern and interest in 4nding a real-world problem that cycled. The oil re4nery problem con-
sidered by Charnes, Cooper and Mellon [7] was an early practical problem that exhibited de-
generacy, but converged without any di6culty. See [4] for further discussion along these
lines.
All commercial LP software that we are aware of apply rules for handling degeneracy, breaking
ties, perturbation techniques, and composite primal and dual computations that enable the computer-
based simplex algorithm to converge to an optimal solution even if the given problem exhibits
classical cycling. In the past, we found one such problem that cycled when operated on by a
popular LP software system. When this was brought to the attention of the software developers, the
next version of the software solved the problem in question. We were not made privy to the changes
that were made. See Benichou et al. [8] for an example of how mathematical programming systems
guard against cycling.
 S.I. Gass, S. Vinjamuri / Computers & Operations Research 31 (2004) 303 311 305

2. Facts about LP problems with respect to cycling

To date, a number of LP problems have been constructed that exhibit classical cycling. We list
and discuss those that we have found in Section 4 (Vinjamuri [9]). If one attempts to construct such
a problem, certain characteristics must be kept in mind. The form of the LP problem is
Minimize cy
subject to
Ix + Ay = b
(x; y) 0 (1)
where I is an (m m) identity matrix, A is an [(m n m)] matrix, (m n), x and y are column
vectors, c is a row vector, and b is a column vector. The basic simplex algorithm is applied to (1)
in which ties for the pivot column are broken by selecting the leftmost (smallest index) column,
and ties for the pivot row are broken by selecting the topmost row (lowest index).
Under the above rules, using the primal simplex, for cycling to occur we must have m 2,
n m+3, and n 6. For cycling to occur at a nonoptimal point we must have m 3, n m+3, and
n 7. All bounds are sharp (Marshall and Suurballe [10]). An LP problem with only two nonbasic
variables cannot cycle; a cycling example must have at least six variables, at least two equations,
and at least three nonbasic variables [10]. A basic feasible solution with a single degeneracy cannot
cause a cycle (due to L. Goldstein, Gass [11]). The minimum length of a cycle is six iterations
(Yudin and Golshtein [12]).

3. The Ho man problem [3]

Conceived by HoHman in 1951, this is the 4rst linear-programming problem that was shown to cy-
cle under the standard simplex iteration rules. It thus demonstrated that anti-cycling or anti-degeneracy
procedures would be necessary to ensure that the theoretical simplex method could be interpreted as
an algorithm that always returned a solution to the problem, that is, stopped after a 4nite number
of steps with a statement of infeasibility or optimal bounded or unbounded solution.
HoHmans problem:
Minimize
[(cos 1)= cos ]x4 + wx5 + 2wx7 + 4 sin2 x8 + w(2 4 cos2 )x9 + 4 sin2 x10
+w(1 2 cos )x11
subject to
x1 = 1
x2 + cos x4 w cos x5 + cos 2x6 2w cos2 x7 + cos 2 x8 + 2w cos2 x9 + cos x10
+w cos x11 = 0
306 S.I. Gass, S. Vinjamuri / Computers & Operations Research 31 (2004) 303 311

x3 + [(tan sin )=w]x4 + cos x5 + [(tan sin 2)=w]x6 + cos 2x7 [2 sin2 =w]x8
+cos 2x9 [(tan sin )=w]x10 + cos x11 = 0
xj 0 for j = 1; : : : ; 11:
Here we set = 2=5; w is any number greater than (1 cos )=(1 2 cos ).
The standard simplex algorithm applied to the above example cycles in 10 iterations without
indicating that the starting basic feasible solution (x1 = 1; x2 = 0; x3 = 0) and all subsequent bases
yield the minimum value of zero for the objective function. Lee [13] discusses and suggests a
possible genesis of HoHmans problem from both algebraic and geometric points-of-view. As noted
in [3], Gass and Jacobs showed the set of 2 2 matrices formed by the second and third rows and
successive pairs of columns form a cyclic set. That is, with


cos w cos
A=
(tan sin )=w cos
formed by the second and third rows with the fourth and 4fth columns, we have A2 corresponding to
(2 2) matrix associated with the sixth and seventh columns, A3 with the eighth and ninth columns,
A4 with the tenth and eleventh columns, and A5 = I [9]. It would appear that such matrices of 4nite
order can be used to construct other cycling problems.

4. Cycling problems

We collected a number of LP problems that exhibit classical cycling and ran each one using three
popular and readily available LP software packages: LINDO, C-Plex, and the Excel spreadsheet
solver. All problems were solved correctly by each package. The problem by Beale was the 4rst
one given in terms of rational coe6cients. For each problem, we note the number of iterations that
returns the problem to its original form, that is, the number of iterations it takes to cycle when the
problem is solved by hand using the standard simplex rules. When 4nding an optimal solution for
these cycling problems using LP software, the iteration count does not reQect the cycle count. For
example, the problem of Section 4.3 cycles in 6 iterations, but is solved by LINDO in one iteration.
Some of the problems have multiple optimal solutions; we list only one.

4.1. Ho7man(See Section 3 for original statement of the problem)

 = 52 
w (1 cos())=(1 2) cos()) 1:8090
w=2
Minimize
2:2361x4 + 2x5 + 4x7 + 3:6180x8 + 3:236x9 + 3:6180x10 + 0:764x11
subject to
 S.I. Gass, S. Vinjamuri / Computers & Operations Research 31 (2004) 303 311 307

x1 = 1
x2 + 0:3090x4 0:6180x5 0:8090x6 0:3820x7 + 0:8090x8 + 0:3820x9 + 0:3090x10
+0:6180x11 = 0
x3 + 1:4635x4 + 0:3090x5 + 1:4635x6 0:8090x7 0:9045x8 0:8090x9 + 0:4635x10
+0:309x11 = 0
xj 0
Solution : x1 = 1; xj = 0 (j = 2; : : : ; 11); Minimum = 0; Cycle = 10:

4.2. Beale example (Gass [2])

Minimize 3=4x1 + 150x2 1=50x3 + 6x4

subject to
1 1
x
4 1
60x2 x
25 3
+ 9x4 + x5 = 0
1 1
x
2 1
90x2 x
50 3
+ 3x4 + x6 = 0

x3 + x7 = 1

xj 0
1 3 1
Solution : x1 = 25
; x3 = 1; x5 = 100
; Minimum = 20 ; Cycle = 6:

4.3. Yudin and Golshtein [12]

Maximize x3 x4 + x 5 x6

subject to

x1 + 2x3 3x4 5x5 + 6x6 = 0

x2 + 6x3 5x4 3x5 + 2x6 = 0

3x3 + x4 + 2x5 + 4x6 + x7 = 1

xj 0

Solution : x1 = 2:5; x2 = 1:5; x5 = 0:5; Maximum = 0:5; Cycle = 6:

308 S.I. Gass, S. Vinjamuri / Computers & Operations Research 31 (2004) 303 311

4.4. Yudin and Golshtein [12]

Maximize x3 x4 + x5 x6
subject to
x1 + x3 2x4 3x5 + 4x6 = 0
x2 + 4x3 3x4 2x5 + x6 = 0
x3 + x4 + x5 + x6 + x7 = 1
xj 0
Solution : x1 = 3; x2 = 2; x5 = 1; Maximum = 1; Cycle = 6:

4.5. Kuhn example (Balinski and Tucker [14])

Minimize 2x4 3x5 + x6 + 12x7

subject to

x1 2x4 9x5 + x6 + 9x7 = 0

x2 + 1=3x4 + x5 1=3x6 2x7 = 0

x3 + 2x4 + 3x5 x6 12x7 = 2

xj 0

Solution : x1 = 2; x4 = 2; x6 = 2; Minimum = 2; Cycle = 6:

Note: The third equation has been added as a bound on the objective function. Without it, the
two equation problem is unbounded and cycles in six iterations.

4.6. Marshall and Suurballe [10]

Minimize 2x1 + 4x4 + 4x6

subject to

x1 3x2 x3 x4 x5 + 6x6 = 0

2x2 + x3 3x4 x5 + 2x6 = 0

xj 0

Solution : All variables = 0; Minimum = 0; Cycle = 6:

 S.I. Gass, S. Vinjamuri / Computers & Operations Research 31 (2004) 303 311 309

4.7. Marshall and Suurballe [10]

Minimize 0:4x5 0:4x6 + 1:8x7

subject to
x1 + 0:6x5 6:4x6 + 4:8x7 = 0
x2 + 0:2x5 1:8x6 + 0:6x7 = 0
x3 + 0:4x5 1:6x6 + 0:2x7 = 0
x 4 + x6 = 1
xj 0
Solution : x1 = 4; x2 = 1; x5 = 4; x6 = 1; Minimum = 2; Cycle = 6:

4.8. Solow [15]

Minimize 2x3 2x4 + 8x5 + 2x6

subject to

x1 7x3 3x4 + 7x5 + 2x6 = 0

x2 + 2x3 + x4 3x5 x6 = 0

xj 0

Solution : All xi = 0; Minimum = 0; Cycle = 6:

4.9. Sierksma [16]

Maximize 3x1 80x2 + 2x3 24x4

subject to

x1 32x2 4x3 + 36x4 + x5 = 0

x1 24x2 x3 + 6x4 + x6 = 0

xj 0

Solution : Unbounded; Cycle = 6:

310 S.I. Gass, S. Vinjamuri / Computers & Operations Research 31 (2004) 303 311

4.10. ChvDatal [17]

Minimize 10x1 57x2 9x3 24x4
subject to
0:5x1 5:5x2 2:5x3 + 9x4 + x5 = 0
0:5x1 1:5x2 0:5x3 + x4 + x6 = 0
x1 + x7 = 1
xj 0
Solution : x1 = 1; x3 = 1; x5 = 2; Minimum = 1; Cycle = 6:

4.11. Nering and Tucker [18]

Maximize 3x2 + x3 6x4 4x6
subject to
x1 + x2 + 1=3x5 + 1=3x6 = 2
9x2 + x3 9x4 2x5 1=3x6 + x7 = 0
x2 + 1=3x3 2x4 1=3x5 1=3x6 + x8 = 2
xj 0
Solution : Unbounded; Cycle = 6:

5. Summary

In the real world of computer-based solutions, the question of cycling in linear-programming prob-
lems has been resolved for all practical purposes. Todays commercial mathematical programming
systems (MPS) have been designed to overcome any chance that a degenerate linear-programming
problem would cycle. There have been and probably will be instances when an MPS will not
converge, but such situations will certainly be due to problems of numerical instability and related
di6culties, not degeneracy. Of course, for large problems, unless they are solved in terms of rational
arithmetic, we will never really know if a problem that exhibits computer cycling will also be subject
to classical cycling.

References

[1] Dantzig G. Linear programming and extensions. Princeton, NJ: Princeton University Press, 1963.
[2] Gass SI. Linear programming: methods and applications, 5th ed. New York: McGraw-Hill Book Company, 1985.
[3] HoHman AJ. Cycling in the simplex algorithm, 1953. Washington, DC: National Bureau of Standards, 1953.
[4] Gass SI. Comments on the possibility of cycling with the simplex method. Operations Research 1979;27(4):84852.
 S.I. Gass, S. Vinjamuri / Computers & Operations Research 31 (2004) 303 311 311

[5] Beale EML. Cycling in the dual simplex method. Naval Research Logistics Quarterly 1955;2(4):26975.
[6] Gassner BJ. Cycling in the transportation problem. Naval Research Logistics Quarterly 1964;11(1):4357.
[7] Charnes A, Cooper WW, Mellon R. Blending aviation gasolinesa study in programming interdependent activities
in an integrated oil company. Econometrica 1952;20(2):13559.
[8] Benichou M, Gauthier JM, Hentges G, RibiTere G. The e6cient solution of large-scale linear programming problems
some algorithmic techniques and computational results. Mathematical Programming 1977;13:280322.
[9] Vinjamuri S. Cycling in linear programming problems. MA Thesis, Department of Mathematics, University of
Maryland, College Park, MD, 1998.
[10] Marshall KT, Suurballe JW. A note on cycling in the simplex method. Naval Research Logistics Quarterly
1969;16(1):12137.
[11] Gass SI. Encounters with degeneracy: a personal view. Annals of Operations Research 1993;47:33542.
[12] Yudin DB, Golshtein EG. Linear programming. Israel Program of Scienti4c Translations, Jerusalem, 1965.
[13] Lee J. HoHmans circle updated. SIAM Review 1997;39:98105.
[14] Balinski ML, Tucker AW. Duality theory of linear programsa constructive approach with applications. SIAM
Review 1997;11:3.
[15] Solow D. Linear programming: an introduction to 4nite improvement algorithms. Amsterdam: North-Holland, 1984.
[16] Sierksma G. Linear and integer programming, 2nd ed. New York: Marcel Dekker, Inc., 1996.
[17] ChvVatal V. Linear programming. New York: W. H. Freeman and Company, 1983.
[18] Nering ED, Tucker AW. Linear programs and related problems. Boston, MA: Academic Press, 1993.

Saul I. Gass received his B.S. in Education and M.A. in Mathematics from Boston University, and his Ph.D. in En-
gineering Science/Operations Research from the University of California, Berkeley. He is currently Professor Emeritus
at the Robert H. Smith School of Business, University of Maryland, College Park. Included in his many publications
are the text Linear Programming (4fth edition), the book An Illustrated Guide to Linear Programming, and the text
Decision Making, Models and Algorithms. He is co-editor of the Encyclopedia of Operations Research and Management
Sciences. His research interests include: linear programming, large-scale systems, model validation and evaluation, game
theory, multi-objective decision analysis, and the application of operations research methodologies.
Sasirekha Vinjamuri received her B.S. and M.A. in Mathematics from the University of Madras. She continued her
studies at the University of Maryland, College Park, where she received an M.A. in Applied Mathematics.