J.A.J. Hall and K.I.M. McKinnon
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.