Gigaflops in Linear Programming

Irvin J. Lustig and Edward Rothberg

This paper describes the parallelization of an ``industrial strength'' linear programming package. Our parallel version of CPLEX barrier, running on a Silicon Graphics Power Challenge shared-memory multiprocessor, provides dramatic performance improvements over sequential methods on a wide range of practical, realistic linear programming problems. The resulting software/hardware combination can provide sustained performance of as much as 2 Gflops.

Operations Research Letters, Vol 18(4), pp. 157-165. Reprints are available from the authors.