Optimization Online



Gavriel Yarmish (yarmish***at***sci.brooklyn.cuny.edu)
Richard Van Slyke (rvslyke***at***poly.edu)

Abstract: 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.

Keywords: linear programming; standard simplex method; dense matrices; distributed computing; parallel optimization

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )


Download: [PDF]

Entry Submitted: 07/31/2005
Entry Accepted: 07/31/2005
Entry Last Modified: 08/31/2005

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society