Fast Descent Methods for LPs With No Matrix Inversions

Katta G. Murty

Abstract


Existing software implementations for solving Linear Programming (LP) models are all based on full matrix inversion operations involving every constraint in the model in every step. This linear algebra component in these systems makes it difficult to solve dense models even with moderate size, and it is also the source of accumulating roundoff errors affecting the accuracy of the output.
We present a new Sphere method, SM-6, for LP not using any pivot steps. The method is currently undergoing computational tests.

Full Text:

PDF Untitled


Algorithmic Operations Research. ISSN: 1718-3235