A parallel revised simplex solver for large scale block angular LP problems

Computational Management Science 10 - Vienna: 29th July 2010

J. A. J. Hall and E. Smith


The revised simplex method is frequently the most efficient method of solving linear programming (LP) problems. Current architecture trends dictate that exploiting parallelism must be considered as a means of improving computational performance. LP problems with block angular structure (BALP problems) occur naturally in decentralized planning models and when solving stochastic programming problems. Graph partitioning can identify block angular structure in more general LP problems. This talk will describe techniques by which the structure of BALP problems can be used to exploit task and data parallelism within a variant of the revised simplex method. Each computational component will be built from serial kernels that exploit sparsity and hyper-sparsity. Thus the resulting implementation is expected to be competitive with high performance serial revised simplex solvers.

PDF CMS10.pdf