|Type of publication:||Article|
|Title||Highly Scalable Parallelization of Standard Simplex Method on a Myrinet Connected Cluster Platform|
|Bibtex cite ID||RACTI-RU1-2014-17|
|Journal ||ACTA Intl Journal of Computers and Applications|
|Year published ||2014|
|Keywords ||Parallel processing,linux clusters,linear programming,simplexalgorithm,message passing interface|
The simplex method has been successfully used in solving linear programming problems for many years. Parallel approaches have also extensively been studied due to the intensive computations required, especially for the solution of large linear problems (LPs). In this paper we present a highly scalable parallel implementation framework of the standard full tableau simplex method on a highly parallel (distributed memory) environment. Speciﬁcally, we have designed and implemented a suitable column distribution scheme as well as a row distribution scheme and we have entirely tested our implementations over a considerably powerful distributed platform (linux cluster with myrinet interface). We then compare our approaches (a) among each other for variable number of problem size (number of rows and columns) and (b) to other recent and valuable corresponding eﬀorts in the literature. In most cases, the column distribution scheme performs quite/much better than the row distribution scheme. Moreover, both schemes (even the row distribution scheme over large-scale problems) lead to particularly high speedup and eﬃciency values, which are considerably better in all cases than the ones achieved in other similar research eﬀorts and implementations. Moreover, we further evaluate our basic parallelization scheme over very large LPs in order to validate more reliably the high eﬃciency and scalability achieved.