A DISTRIBUTED, SCALEABLE SIMPLEX METHOD

We present a simple, scaleable, distributed simplex implementation for large linear programs. It is designed for coarse grained computation, particularly, readily available networks of workstations. Scalability is achieved by using the standard form of the simplex rather than the revised method. Virtually all serious implementations are based on the revised method because it is much faster for sparse LPs, which are most common. However, there are advantages to the standard method as well. First, the standard method is effective for dense problems. Although dense problems are uncommon in general, they occur frequently in some important applications such as wavelet decomposition, digital filter design, text categorization, and image processing. Second, the standard method can be easily and effectively extended to a coarse grained, distributed algorithm. Such an implementation is presented here. The effectiveness of the approach is supported by experiment and analysis.

Article

Download

View PDF