Many classes of continuous linear programming (LP) problems and families of related LP problems, such as relaxations of MIP problems, are generally solved using the dual revised simplex method. Despite its potential value, there has been relatively little research into the development of implementations of the revised simplex method which exploit parallel computing environments. Hitherto these efforts have met with very limited success, in particular for general large sparse LP problems.
This talk introduces the design and implementation of a parallel dual simplex solver PAMI for general large scale sparse LP problems. This extends a relatively unknown pivoting strategy called suboptimization and exploits parallelism across multiple iterations. The work has required the development of techniques for both algorithmic control and large scale sparse numerical linear algebra. The focus of this talk will be the latter.
Computational results show that the performance of PAMI is superior to that of Clp, the leading open-source serial simplex solver. One of the authors has implemented the techniques underlying PAMI within the FICO Xpress simplex solver and results demonstrating their value will be presented.
| NLAO16.pdf |
Parallelizing the dual revised simplex method
Q. Huangfu and J. A. J. Hall
Accepted for publication in Mathematical Programming Computation
Technical Report ERGO-14-011.