Comparisons of Composite Simplex Algorithms

摘要

For almost forty years, the simplex method has been the method of choice for solving linear programs. The method consists of first finding a feasible solution to the problem (Phase I), followed by finding the optimum (Phase II). Many algorithms have been proposed which try to combine the processes embedded in the two-phase process. This study will compare the merits of some of these composite algorithms. Theoretical and computational aspects of the Weighted Objective, Self-Dual Parametric, and Markowitz Criteria algorithms are presented. Different variants of the Self-Dual methods are discussed. A large amount of computational experience for each algorithm is presented. These results are used to compare the algorithms in various ways. The implementations of each algorithm are also discussed. One theme that is present throughout all of the computational experience is that there is no one algorithm which is the best algorithm for all problems.