#
Parallel solution of block angular LP problems using Kaul's algorithm

###
School of Mathematics ERGO seminar: 7th November 2007

###
İ. İ. Boduroğlu, J. A. J. Hall and J. D. Hogg

####
Abstract

Block-angular LP problems arise in many important applications, from
finance to animal feed formulation. This talk introduces Kaul's
algorithm, an old but little known variant of the simplex method for
block-angular LP problems. When implemented using dense data
structures, it can be viewed as a hybrid of the standard and revised
simplex method, restricting the dense matrix algebra to arrays with at
most one dimension equal to that of the LP problem. This offers
significant scope for efficient parallel implementation. However,
unlike the standard simplex method, this would not be achieved by
starting from a serial performance that is so wholly uncompetitive
with that of a good revised simplex solver. A sparsity-exploiting
implementation of Kaul's algorithm would correspond to the revised
simplex method with the structure of the original LP exploited by the
basis matrix inverse. This variant and the scope for its parallel
implementation will be described.

**Slides:**