research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:chita
TitleHighly Scalable Parallelization of Standard Simplex Method on a Myrinet Connected Cluster Platform
Bibtex cite IDRACTI-RU1-2014-17
Journal ACTA Intl Journal of Computers and Applications
Year published 2014
DOI 10.2316/journal.202.2013.4.202-3691
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. Specifically, 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 efforts 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 efficiency values, which are considerably better in all cases than the ones achieved in other similar research efforts and implementations. Moreover, we further evaluate our basic parallelization scheme over very large LPs in order to validate more reliably the high efficiency and scalability achieved.
Mamalis, Basilis
Pantziou, Grammati
Dimitropoulos, G.
Kremmydas, D.
Publication ID1032