#
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

####
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 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.

**Slides:**