individual-entry-BA-Blog

« Decisions in the Cloud | Main | Analytics and Big Data are Key Technology Trends for 2013 »

Celebrating 40 Years of Forrest-Tomlin

Simplex_algorithm
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.

 

First time on the EDM blog?
Subscribe to the EDM blog feed or check out some other recent posts:

TrackBack

TrackBack URL for this entry:
http://www.typepad.com/services/trackback/6a00d83451629b69e2017d3cac61d3970c

Listed below are links to weblogs that reference Celebrating 40 Years of Forrest-Tomlin:

Comments

The comments to this entry are closed.

Search Site


  • dmblog.fico.com

Subscribe

  • enter your email

Upcoming Events

  • FICO Tools & Analytics User Forum 2012
    BERLIN: September 11-12, 2012 LONDON: September 18-19, 2012 Gain new insights for improving business performance through advanced analytics and decision management tools.