ABSTRACT

The Simplex Method, the most popular method for solving Linear Programs (LPs), has two major variants. They are the revised method and the standard, or full
tableau method. Today, virtually all serious implementations are of the revised method because it is more efficient for sparse LPs which are the most common.
However, the full tableau method has advantages as well. First, the full tableau can be very effective for dense problems. Second, a full tableau method can
easily and effectively be extended to a coarse grained distributed algorithm. While dense problems are uncommon in general, they occur frequently in some important
applications such as digital filter design, text categorization, image processing and relaxations of scheduling problems. We implement two full tableau algorithms. The first, a serial implementation, is effective for small to moderately sized dense problems. The second, a simple extension of the first, is a distributed algorithm, which is effective for large problems of all densities. We developed performance models that predict running times per iteration for the serial version of our method, the parallel version of our method and the revised method for problems of different sizes, aspect ratios and densities. We also developed methods for choosing the number of processors to optimize the tradeoff between computation and communication in distributed computations. We tested our algorithms on practical (Netlib) and synthetic problems.