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 ().-->