Basilis Mamalis, Grammati Pantziou, Georgios Dimitropoulos, and Dimitrios Kremmydas
Linear Programming, Simplex Algorithm, Parallel Processing, MPI Linux Clusters
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 computatios required (especially for the solution of large in size linear problems). In this paper we present a highly scaleable parallel implementation framework of the standard full tableau simplex method on a highly parallel (distributed memory) environment. Specifically, we have designed and implemented a column distribution scheme (similar to the one presented in [24]) as well as a row distribution scheme (similar to the one presented in [3]) and we have entirely tested our implementations over a considerably powerful parallel environment (a linux-cluster of eight powerful Xeon processors connected via a high speed Myrinet network interface). We then compare our approaches (a) among each other for variable number of problem size (number of rows and columns) and (b) to the corresponding ones of [3] and [24] which are two of the most recent and valuable corresponding efforts. 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 speed-up and efficiency values, that are considerably better in all cases than the ones achieved by the corresponding implementations of [3] and [24].
Important Links:
Go Back
