PARSMI, a parallel revised simplex algorithm incorporating minor iterations and Devex pricing. When solving linear programming problems using the revised simplex method, two common variants are the incorporation of minor iterations of the standard simplex method applied to a small subset of the variables and the use of Devex pricing. Although the extra work per iteration which is required when updating Devex weights removes the advantage of using minor iterations in a serial computation, the extra work parallelises readily. An asynchronous parallel algorithm PARSMI is presented in which computational components of the revised simplex method with Devex pricing are either overlapped or parallelism is exploited within them. Minor iterations are used to achieve good load balance and tackle problems caused by limited candidate persistence. Initial computational results for an six-processor implementation on a Cray T3D indicate that the algorithm has a significantly higher iteration rate than an efficient sequential implementation.
Keywords for this software
References in zbMATH (referenced in 7 articles )
Showing results 1 to 7 of 7.
- Huangfu, Q.; Hall, J. A. J.: Parallelizing the dual revised simplex method (2018)
- Tar, Péter; Stágel, Bálint; Maros, István: Parallel search paths for the simplex algorithm (2017)
- Mamalis, Basilis; Pantziou, Grammati: Advances in the parallelization of the simplex method (2015)
- Ploskas, Nikolaos; Samaras, Nikolaos: Efficient GPU-based implementations of simplex type algorithms (2015)
- -: COAP 2013 Best Paper Prize (2014)
- Ploskas, Nikolaos; Samaras, Nikolaos; Margaritis, Konstantinos: A parallel implementation of the revised simplex algorithm using OpenMP: some preliminary results (2013)
- Hall, J. A. J.: Towards a practical parallelisation of the simplex method (2010)