J.A.J. Hall and K.I.M. McKinnon
Abstract
In the parallel revised simplex method proposed by Hall and McKinnon, the inversion of basis matrices
is perfomed in parallel with the simplex iterations.
As a result the update procedure must accommodate the set of basis changes which have occurred since commencing the inversion.
This paper shows that update procedures which modify the factors of the matrix which is inverted are inappropriate for the
parallel revised simplex method and that either the product form or an update based on the use of a Schur complement should be
used.
The essential difference between these approaches is highlighted and the implementation of the product form within the
parallel revised simplex method is shown to be straightforward.
Two approaches to the problem of using an update based on a Schur complement in the parallel revised simplex method are
described.
Key words: Linear programming, revised simplex method, parallelism, basis update.