Research ArticleOpen AccessGoogle Scholar indexed
A Computational Comparison of Basis Updating Schemes for the Simplex Algorithm on a CPU-GPU System
Department of Applied Informatics, School of Information Sciences, University of Macedonia, Thessaloniki, Greece
Department of Applied Informatics, School of Information Sciences, University of Macedonia, Thessaloniki, Greece
- 1 Department of Applied Informatics, School of Information Sciences, University of Macedonia, Thessaloniki, Greece
- 2 Department of Applied Informatics, School of Information Sciences, University of Macedonia, Thessaloniki, Greece
American Journal of Operations Research·Volume 03 (2013)·Pages 497–505·Published 24 October 2013·DOI10.4236/ajor.2013.36048
Copy link · social · email
Abstract
The computation of the basis inverse is the most time-consuming step in simplex type algorithms. This inverse does not have to be computed from scratch at any iteration, but updating schemes can be applied to accelerate this calculation. In this paper, we perform a computational comparison in which the basis inverse is computed with five different updating schemes. Then, we propose a parallel implementation of two updating schemes on a CPU-GPU System using MATLAB and CUDA environment. Finally, a computational study on randomly generated full dense linear programs is preented to establish the practical value of GPU-based implementation.
KeywordsSimplex AlgorithmBasis InverseGraphics Processing UnitMATLABCompute Unified Device Architecture
- G. B. Dantzig and W. Orchard-Hays, “The Product Form of the Inverse in the Simplex Method,” Mathematics of Computation, Vol. 8, 1954, pp. 64-67. http://dx.doi.org/10.1090/S0025-5718-1954-0061469-8
- M. Benhamadou, “On the Simplex Algorithm ‘Revised Form’,” Advances in Engineering Software, Vol. 33, No. 11, 2002, pp. 769-777. http://dx.doi.org/10.1016/S0965-9978(02)00037-6
- R. K. Brayton, F. G. Gustavson and R. A. Willoughby, “Some Results on Sparse Matrices,” Mathematics of Computation, Vol. 24, No. 115, 1970, pp. 937-954. http://dx.doi.org/10.1090/S0025-5718-1970-0275643-8
- H. Markowitz, “The Elimination Form of the Inverse and Its Applications to Linear Programming,” Management Science, Vol. 3, No. 3, 1957, pp. 255-269. http://dx.doi.org/10.1287/mnsc.3.3.255
- R. H. Bartels and G. H. Golub, “The Simplex Method of Linear Programming Using LU Decomposition,” Communications of the ACM, Vol. 12, No. 5, 1969, pp. 266268.
- J. J. H. Forrest and J. A. Tomlin, “Updated Triangular Factors of the Basis to Maintain Sparsity in the Product Form Simplex Method,” Mathematical Programming, Vol. 2, No. 1, 1972, pp. 263-278. http://dx.doi.org/10.1007/BF01584548
- J. Reid, “A Sparsity-Exploiting Variant of the BartelsGolub Decomposition for Linear Programming Bases,” Mathematical Programming, Vol. 24, No. 1, 1982, pp. 55-69. http://dx.doi.org/10.1007/BF01585094
- L. M. Suhl and U. H. Suhl, “A Fast LU Update for Linear Programming,” Annals of Operations Research, Vol. 43, No. 1, 1993, pp. 33-47. http://dx.doi.org/10.1007/BF02025534
- M. Saunders, “A Fast and Stable Implementation of the Simplex Method Using Bartels-Golub Updating,” In: J. Bunch and S. T. Rachev, Eds., Sparse Matrix Computation, Academic Press, New York, 1976, pp. 213-226.
- D. Goldfarb, “On the Bartels-Golub Decomposition for Linear Programming Bases,” Mathematical Programming, Vol. 13, No. 1, 1977, pp. 272-279. http://dx.doi.org/10.1007/BF01584343
- J. L. Nazareth, “Computer Solution of Linear Programs,” Oxford University Press, Oxford, 1987.
- V. Chvatal, “Linear Programming,” W. H. Freeman and Company, New York, 1983.
- P. F. McCoy and J. A. Tomlin, “Some Experiments on the Accuracy of Three Methods of Updating the Inverse in the Simplex Method,” Technical Report, Stanford University, Stanford, 1974.
- S. Lim, G. Kim and S. Park, “A Comparative Study between Various LU Update Methods in the Simplex Method,” Journal of the Military Operations Research Society of Korea, Vol. 29, No. 1, 2003, pp. 28-42.