#
Towards Reliable Linear Programming

###
Technical Report NA/120, Department of Mathematics and Computer Science, University of Dundee.

###
Pitman Research Notes in Mathematics Series 228, 89-104, eds G.A. Watson and D.F. Griffiths, Longman Scientific and Technical, 1990.

**
R. Fletcher and
J.A.J. Hall
**

**
Abstract
**

Difficulties with simplex-like methods for linear programming arise when
degeneracy and round-off errors interact to cause cycling and other
instances of non-termination. This paper develops a method described by
Fletcher (*Linear Algebra Appl.* **106**, 149-183, 1988)
which guarantees termination under these circumstances. The method may
truncate small numbers to zero in a near-degenerate situation in order to
obtain exact degeneracy which is then treated accordingly.

In certain situations it has been observed that more significant truncations
can arise and some examples of this are illustrated. In one situation, a
pivot on a small number, whose magnitude is comparable to the round-off
error, can cause a large truncation to occur at a later stage. Thus a
strategy for truncating small potential pivots has been adopted in order to
avoid large truncations occurring. Another extension of the method of Fletcher is ...

**
Key words:
**
Linear programming, degeneracy, reliability, Schur complement update.
).

Compressed Postscript NA124.ps.Z ().

G-Zipped Postscript NA124.ps.gz ().-->