High performance numerical linear algebra for the revised simplex method

Plenary talk at NLAO18: 6th IMA Conference on Numerical Linear Algebra and Optimization, 27-29 June 2018

Julian Hall

Abstract

Numerical linear algebra and optimization techniques are combined in high performance implementations of the revised simplex method to solve linear programming (LP) problems. For most problems of practical interest, computational performance depends on enhancements of the classical simplex algorithm and efficient solution of linear systems of equations, for which the coefficient matrix is large, sparse and asymmetric. After identifying the characteristics of these linear systems which define the challenge of solving them efficiently, this talk will review the state of the art of the corresponding serial and parallel computational techniques, for both general and structured LP problems.

Slides:

NLAO18.pdf

Code:

HiGHS

Papers:

• A quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems
  I. L. Galabova and J. A. J. Hall
  Technical Report ERGO-18-009
  Submitted to Optimization Methods and Software

• Parallelizing the dual revised simplex method
  Q. Huangfu and J. A. J. Hall
  Technical Report ERGO-14-011
  Mathematical Programming Computation, 10 (1), 119-142, 2018. DOI: 10.1007/s12532-017-0130-5

• Novel update techniques for the revised simplex method
  Q. Huangfu and J. A. J. Hall
  Technical Report ERGO-13-001
  Computational Optimization and Applications 60(3), 587-608, 2015. DOI: 10.1007/s10589-014-9689-1
  Awarded the prize for the best paper of 2015 in Computational Optimization and Applications

• Parallel distributed-memory simplex for large-scale stochastic LP problems
  M. Lubin, J. A. J. Hall, C. G. Petra and M. Anitescu
  Technical Report ERGO-12-005
  Computational Optimization and Applications 55(3), 571-596, 2013. DOI: 10.1007/s10589-013-9542-y
  Awarded the COIN-OR INFORMS 2013 Cup on 7 October 2013
  Awarded the prize for the best paper of 2013 in Computational Optimization and Applications

• Hyper-sparsity in the revised simplex method and how to exploit it
  J. A. J. Hall and K. I. M. McKinnon
  Hyper-sparsity October 2002
  Computational Optimization and Applications 32(3), 259-283, 2005. DOI: 10.1007/s10589-005-4802-0
  Awarded the prize for the best paper of 2005 in Computational Optimization and Applications