ABSTRACT

Dantzig's simplex algorithm for linear programming has two major variants: the original, or standard method, and the revised method. Today, virtually all serious implementations are based on 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 is effective for dense problems. 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. 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.) Finally, as we shall show here, simple and accurate models of iteration times are available for standard simplex method implementations.