A parallel implementation of an exterior point algorithm for linear programming problems
Νικόλαος Πλόσκας, Nikolaos Samaras, Angelo Sifaleras · 2009
The simplex method is perhaps the most widely used method for solving linear programming (LP) problems. The computation time of simplex type algorithms depends on the basis inverse that occurs in each iteration. Parallelizing simplex type algorithms is one of the most challenging problems. The aim of this paper is to p resent a parallel implementation of the primal exterior poin t simplex algorithm. In this approach the basis inverse is co mputed in parallel. The matrix that holds the basis is distrib uted among different workers and the computation is performed faster in large-scale LP problems. Apart from the pa rallel implementation, this paper presents a computational study that shows the speedup among the serial and parallel version in large-scale randomly generated full dens e LP problems.