Parallel revised simplex for primal block angular LP problems

Contributed talk at PMAA 2012, Birkbeck University of London, UK: 28th June 2012

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 row linked block angular structure (primal BALP problems) occur naturally in decentralized planning models. Hyper-graph partitioning can identify block angular structure in more general LP problems. This talk will describe techniques by which the structure of primal BALP problems can be used to exploit task and data parallelism within a variant of the revised simplex method. Each computational component is built from serial kernels that exploit sparsity and hyper-sparsity. Results for a prototype implementation will be presented.

PDF PMAA12.pdf