Some Computational Results on MPI Parallel Implementation of Dense Simplex Method
There are two major variants of the Simplex
Algorithm: the revised method and the standard, or tableau method.
Today, all serious implementations are based on the revised method
because it is more efficient for sparse linear programming problems.
Moreover, there are a number of applications that lead to dense linear
problems so our aim in this paper is to present some computational
results on parallel implementation of dense Simplex Method. Our
implementation is implemented on a SMP cluster using C
programming language and the Message Passing Interface MPI.
Preliminary computational results on randomly generated dense
linear programs support our results.
[1] G. B. Dantzig, Linear Programming and Extensions. NJ: Princeton,
Princeton University Press, 1963.
[2] K. H. Borgwardt, "Some distribution independent results about the
asymptotic order of the average number of pivot steps in the simplex
method", Mathematics of Operations Research, vol. 7, no. 3, pp. 441-
462, 1982.
[3] I. Maros, and G. Mitra, "Investigating the sparse simplex method on a
distributed memory multiprocessor", Parallel Computing, vol. 26, pp.
151-170, 2000.
[4] D. Klabjan, L. E. Johnson, and L. G. Nemhauser, "A parallel primal-dual
simplex algorithm", Operations Research Letters, vol. 27, no. 2, pp. 47-
55, 2000.
[5] J. Eckstein, I. Bodurglu, L. Polymenakos, and D. Goldfarb, "Data-
Parallel Implementations of Dense Simplex Methods on the Connection
Machine CM-2", ORSA Journal on Computing, vol. 7, no. 4, pp. 402-
416, 1995.
[6] S. P. Bradley, U. M. Fayyad, and O. L. Mangasarian, "Mathematical
Programming for Data Mining: Formulations and Challenges",
INFORMS Journal on Computing, vol. 11, no. 3, pp. 217-238, 1999.
[7] I. Foster, Designing and Building Parallel Programs: Concepts and
Tools for Parallel Software Engineering. Addison-Wesley, 1995.
[8] W. Gropp, E. Lusk, and A. Skjellum, Using MPI: Portable Parallel
Programming with the Message Passing-Interface. MIT Press, 1994.
[1] G. B. Dantzig, Linear Programming and Extensions. NJ: Princeton,
Princeton University Press, 1963.
[2] K. H. Borgwardt, "Some distribution independent results about the
asymptotic order of the average number of pivot steps in the simplex
method", Mathematics of Operations Research, vol. 7, no. 3, pp. 441-
462, 1982.
[3] I. Maros, and G. Mitra, "Investigating the sparse simplex method on a
distributed memory multiprocessor", Parallel Computing, vol. 26, pp.
151-170, 2000.
[4] D. Klabjan, L. E. Johnson, and L. G. Nemhauser, "A parallel primal-dual
simplex algorithm", Operations Research Letters, vol. 27, no. 2, pp. 47-
55, 2000.
[5] J. Eckstein, I. Bodurglu, L. Polymenakos, and D. Goldfarb, "Data-
Parallel Implementations of Dense Simplex Methods on the Connection
Machine CM-2", ORSA Journal on Computing, vol. 7, no. 4, pp. 402-
416, 1995.
[6] S. P. Bradley, U. M. Fayyad, and O. L. Mangasarian, "Mathematical
Programming for Data Mining: Formulations and Challenges",
INFORMS Journal on Computing, vol. 11, no. 3, pp. 217-238, 1999.
[7] I. Foster, Designing and Building Parallel Programs: Concepts and
Tools for Parallel Software Engineering. Addison-Wesley, 1995.
[8] W. Gropp, E. Lusk, and A. Skjellum, Using MPI: Portable Parallel
Programming with the Message Passing-Interface. MIT Press, 1994.
@article{"International Journal of Information, Control and Computer Sciences:61268", author = "El-Said Badr and Mahmoud Moussa and Konstantinos Paparrizos and Nikolaos Samaras and Angelo Sifaleras", title = "Some Computational Results on MPI Parallel Implementation of Dense Simplex Method", abstract = "There are two major variants of the Simplex
Algorithm: the revised method and the standard, or tableau method.
Today, all serious implementations are based on the revised method
because it is more efficient for sparse linear programming problems.
Moreover, there are a number of applications that lead to dense linear
problems so our aim in this paper is to present some computational
results on parallel implementation of dense Simplex Method. Our
implementation is implemented on a SMP cluster using C
programming language and the Message Passing Interface MPI.
Preliminary computational results on randomly generated dense
linear programs support our results.", keywords = "Linear Programming, MPI, Parallel Implementation,
Simplex Algorithm.", volume = "2", number = "11", pages = "3919-4", }