TOC | Abstract | (1) Intro | (2) Simplex | (3) Impl | (4) Test | (5) Results | (6) Concl | Scripts | Biblio | Author | Chairman |
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
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 Reids 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 MATLABs 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 Reids Method both outperformed the others, but in most situations the Sparse Bartels-Golub Method remained the superior solution.