An efficient steepest-edge simplex algorithm for SIMD computers

This paper proposes a new implementation of the Primal and Dual Simplex algorithms for Linear Programming problems on massively parallel SIMD computers. The algorithms are based on the Steepest-Edge pivot selection method and the tableau representation of the constraint matrix. The parallel algorithm reduces communication overhead by maintaining local replicas of key portions of the tableau along with the sub-matrices on each one of the PEs. The Steepest-Edge method utilizes mainly local information to search for the next pivot element. Pivot rows and columns are efficiently broadcasted to PEs before pivot steps, utilizing the geometry of pipelined, toroidal mesh interconnection network. The proposed parallelization has optimal asymptotic speedup and scalability properties and experimental results show that as problem sizes increase the speedups obtained by MasPar's MP-1 and MP-2 models are in the order of 100 times, and 1000 times, respectively, over sequential Steepest-Edge Simplex running on high-end Unix workstations.

An efficient steepest-edge simplex algorithm for SIMD computers Conference Paper