High performance computing and the simplex method

LANCS Workshop on Modelling and Solving Complex Optimisation Problems: 12th April 2011

J. A. J. Hall, Q. Huangfu and E. Smith


When solving families of related LP problems and many classes of single LP problems, the simplex method is the preferred computational technique. There is, therefore, consid- erable motivation for exploring how the simplex method may exploit modern desktop high performance computing (HPC) architectures. This talk will discuss two approaches by which this may be achieved on multi-core CPUs and many-core GPUs. The rst is to identify LP problem structure that allows the revised simplex method to exploit such architectures, and the second is to develop novel algorithmic variants of the simplex method to facilitate HPC implementations for general LP problems. Results will be presented for two CPU and one GPU implementation, and the scope for exploiting combined CPU and GPU systems will be discussed.

PDF Lancs11.pdf