Chapter 6

Conclusion

The results of these analyses failed to indicate either the Forrest-Tomlin or Reid’s Methods as a complete alternative to the Sparse Bartels-Golub Method. In certain situations one or the other may prove to be effective. Even in those situations where the Forrest-Tomlin Method or Reid’s Method produced fewer non-zero data entries, the Sparse Bartels-Golub Method often managed to perform fewer floating-point operations. Since floating-point calculations require the most CPU time in modern processors, this advantage would become a significant speed advantage in a compiled environment.

The Sparse Bartels-Golub Method also consistently outperformed the original Bartels-Golub Method in terms of floating-point operations and non-zero data entries. Since the only difference between the two methods was essentially their methods of data storage, their comparison shows that efforts to amortize the time-complexity of the Simplex Method can produce real improvements in actual execution. This is the aspect of the Simplex Method on which most research has been done.

However, the performance of the Revised Simplex Method indicates that a new direction in research might prove useful. Despite the known improvement in time-complexity between the Revised Simplex Method and all the other methods tested, the Revised Simplex Method still outperformed the others significantly. Since MATLAB’s internal algorithms take advantage of sparsity, the direct calculation of the inverse of a sparse matrix proved to be far more effective than any improvements made by the other Simplex Method variations. However, the problems used were small-to-medium sized industrial problems. Larger problems could show that this is not the case, however, these algorithms were unable to solve much larger problems on the system they were tested.

In comparison, the various methods of the Simplex Method each have their strength and weaknesses for use in linear programming. The Revised Simplex Method provided a concise implementation although it produced much more data in need of storage than the others. The Bartels-Golub Method reduced that storage by slightly increasing the number of calculations per iteration. The Sparse Bartels-Golub Method and the Forrest-Tomlin Method improved the time-complexity by amortizing the cost over a series of iterations. Finally, Reid’s Method attempted to improve data storage by determining efficient data structures. Altogether, these algorithms showed that much research remains to be done in the field of linear programming.