This year marks the 40th birthday of the Forrest-Tomlin Method, which was implemented to speed up the simplex algorithm for early computer architectures. As many Operations Researchers know, this method is still applicable as one of the fundamental technologies in optimization software.
One of the cornerstones of linear programming is an efficient update of the factorization of the working basis. Many different methods have been tried for implementing this critical function, from the classical product form update, which imitates the steps of Gaussian elimination, to the Bartels-Golub update, which was the first to maintain LU factors directly by partial pivoting. In addition, we have Reid’s method of symbolic sparse updates, Saunders’ method of spike reordering, and Fletcher and Matthews’ work with the Schur complement.
It is not an exaggeration to say that almost all modern implementations are based on the method first devised by John Forrest and John Tomlin, and published in 1972. It combines much of the speed and ease of the product form update with the increased sparsity of the Bartels-Golub update, and was a significant improvement on both. Although many variants have been explored since – Suhl and Suhl’s sparsity exploiting update is a recent example – the basic method remains highly competitive; a remarkable achievement given the changes in computer hardware over that period.
Learn more about the history and implications for today’s implementations at this year’s annual INFORMS meeting. Operations Researchers and Management Sciences specialists will also learn about recent developments in the field and the underlying tools of the profession, such as FICO® Xpress Optimization Suite. Stop by the FICO booth or attend one of our many sessions to learn more.