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.