R. Fletcher and J.A.J. Hall
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 ...
Linear programming, degeneracy, reliability, Schur complement update.
Compressed Postscript NA124.ps.Z ().
G-Zipped Postscript NA124.ps.gz ().-->