Parallelizing the Dual Simplex Method
- 1 February 2000
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 12 (1) , 45-56
- https://doi.org/10.1287/ijoc.12.1.45.11902
Abstract
We study the parallelization of the steepest-edge version of the dual simplex algorithm. Three different parallel implementations are examined, each of which is derived from the CPLEX dual simplex implementation. One alternative uses PVM, one general-purpose System V shared-memory constructs, and one the PowerC extension of C on a Silicon Graphics multi-processor. These versions were tested on different parallel platforms, including heterogeneous workstation clusters, Silicon Graphics multi-processors, and an IBM SP2. We report on our computational experience.Keywords
This publication has 13 references indexed in Scilit:
- Gigaflops in linear programmingOperations Research Letters, 1996
- Steepest-edge simplex algorithms for linear programmingMathematical Programming, 1992
- The network simplex method on a multiprocessorNetworks, 1990
- A Nondeterministic Parallel Algorithm for General Unsymmetric Sparse LU FactorizationSIAM Journal on Matrix Analysis and Applications, 1990
- Unix network programmingACM SIGCOMM Computer Communication Review, 1990
- A practical anti-cycling procedure for linearly constrained optimizationMathematical Programming, 1989
- A parallel algorithm for generalized networksAnnals of Operations Research, 1988
- A parallelization of the simplex methodAnnals of Operations Research, 1988
- Pivot selection methods of the Devex LP codeMathematical Programming, 1973
- Updated triangular factors of the basis to maintain sparsity in the product form simplex methodMathematical Programming, 1972