Novel update techniques for the revised simplex method

Contributed talk at the 15th EUROPT Workshop on Advances in Continuous Optimization, 12-14 July 2017

Julian Hall and Qi Huangfu

Abstract

The development of techniques for creating and updating the invertible representation of the simplex basis matrix were a feature of my PhD studies under Roger in 1987-90. So it is appropriate that this talk presents recent recent work in this area. Specifically, it will describe two variants of the product form update and the multiple Forrest-Tomlin update which are valuable in the context of a recently released high performance revised simplex solver.

Slides:

PDF	EUROPT17.pdf

Papers:

• 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

• Parallelizing the dual revised simplex method
  Q. Huangfu and J. A. J. Hall
  Technical Report ERGO-14-011
  Accepted for publication in Mathematical Programming Computation