retroLP, An Implementation of the Standard Simplex Method
TR-CIS-2001-05
Gavriel Yarmish, Richard Van Slyke

pdf version of this paper

Abstract:
Dantzig's simplex algorithm has two major variants: the original, or standard method, and the revised method. Today, virtually all serious implementations are of the revised method because it is much faster for sparse LPs, which are most common. However, the standard method has advantages as well. First, the standard method can be very effective for dense problems. Second, the standard method can be easily and effectively extended to a coarse grained, distributed algorithm. (There are no scalable distributed versions of the revised simplex method.) While dense problems are uncommon in general, they occur frequently in some important applications such as wavelet decomposition, digital filter design, text categorization, image processing and relaxations of scheduling problems.

In this short paper, we briefly describe a full featured implementation of the standard method, retroLP, which we make available to all for research or educational use. Second, we give performance models of the standard and revised method so that their running times can be compared as a function of a priori problem characteristics such as size, aspect ratio (ratio the number of variables to the number of constraints), and density (fraction of constraint coefficients which are non-zero). Experimental results on synthetic and practical problems are given to estimate the parameters of the models, and to validate their accuracy. Finally, applications of the algorithm are discussed, particularly in support of a scalable, coarse grained, distributed implementation of the simplex method, dpLP [Yarmish, 2001].

retroLP is a full scale implementation of the standard simplex method written in C++ compatible C. It takes input in the MPS format. Our implementation supports virtually all the options for linear programming implied by the format. To preserve numerical stability, our implementation uses full pivoting reinversion. retroLP also uses the EXPAND degeneracy procedure of Gill, Murray, Saunders, and Wright to improve numerical stability and to avoid stalling and degeneracy.