Abstract of Thesis Presented to the Graduate School
of the University of Florida in Partial Fulfillment of the
Requirements for Degree of Master of Science

A Comparison of Simplex Method Algorithms

By

Steven S. Morgan

January, 1997

Chairman: Dr. Timothy A. Davis
Major Department: Computer and Information Science and Engineering

This thesis compares five common implementations of the Revised Simplex Method, a popular algorithm for solving linear optimization problems of the form

The particular implementations includes the original Revised Simplex Method, the Bartels-Golub Method, the Sparse Bartels-Golub Method, the Forrest-Tomlin Method, and Reid’s Method. Each were implemented in MATLAB scripts and tested for total number of floating point operations, maximum data storage, and number of basis refactorizations. The algorithms were tested on a variety of small-sized and medium-sized industrial sparse-matrix problems available via the Internet.

The Revised Simplex Method and the Bartels-Golub Method performed extremely well due to MATLAB’s interpretive environment, however, they suffered from large data storage requirements and they required an excessive number of basis matrix refactorizations. The Sparse Bartels-Golub Method significantly improved on these shortcomings. In other situations, the Forrest-Tomlin Method and Reid’s Method both outperformed the others, but in most situations the Sparse Bartels-Golub Method remained the superior solution.