High performance numerical linear algebra for the revised simplex method
Workshop on Linear Algebra for PDEs and Optimization, 4 September 2017
Julian Hall
Abstract
Solving large scale sparse linear programming problems (LP) efficiently using the revised simplex method depends on the solution of sparse linear systems of equations with related coefficient matrices. Although these coefficient matrices are frequently highly reducible, making their factorization computationally straightforward, this does lead to the the phenomenon of hyper-sparsity being demonstrated for important classes of LP problems. Other classes of LP problems inherit structure from the underlying model allowing parallel computation to be exploited. This talk will describe how hyper-sparsity and problem structure may be exploited, as well as presenting novel techniques for updating the invertible representation of the coefficient matrix which underpin the computational efficiency of the open-source dual revised simplex solver, h2gmp.
Slides:
| LAPDEO17.pdf |