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

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 ().
G-Zipped Postscript ().-->