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
Abstract
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.
Slides: