Chapter 4

Testing

The Netlib linear programming library provides a set of realistic linear programs ranging up to several thousand non-zero entries. These problems are encoded in the industry-standard MPS format. A Perl script was used to interpret the MPS data files and output a MATLAB M-file. This M-file, when run in MATLAB, recreates the linear program in the following matrix form:

The MATLAB M-file scripts used to implement the different algorithms are presented in the Appendix. The Revised-Simplex Method script was developed first and then modified for the Bartels-Golub Method. The other methods were modified from the Bartels-Golub Method script. As a result, each algorithm was implemented with the same steps as the Revised Simplex Method, allowing for easy code comparison.

Also because of the development of these scripts, they each have the same calling interface. This provides that no issues related to equation presentation can affect the results. In addition, a single program can easily test one problem on each of the five methods without any extra effort.

These algorithms were tested on a Sparc 5 using MATLAB version 4.2c. The load on the machine was not constant, so the run-time execution measurements are not reliable and are used herein only for a qualitative analysis. A combination of MATLAB M-files, Unix scripts, and short C programs were used to automate the testing process. The floating-point operation counts are independent of the actual execution time, so they remain an accurate measure of comparison between the algorithms. However, the real-time execution times were heavily dependent on machine load and interpretive overhead which is why they are only somewhat effective for qualitative analysis.

Determining appropriate refactorization threshhold values for the Sparse Bartels-Golub, Forrest-Tomlin, and Reid’s Methods was done by testing a few of the mid-range sized matrices over a range of threshhold values. No one value will serve for every situation, however threshhold values that worked well for most of the situations encountered were fairly easy to determine.