A Computational Comparison of Basis Updating Schemes for the Simplex Algorithm on a CPU-GPU System

Nikolaos Ploskas, Nikolaos Samaras

Department of Applied Informatics, School of Information Sciences, University of Macedonia, Thessaloniki, Greece.

DOI: 10.4236/ajor.2013.36048                

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.

Keywords

Simplex Algorithm; Basis Inverse; Graphics Processing Unit; MATLAB; Compute Unified Device Architecture

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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
[2]	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
[3]	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
[4]	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
[5]	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.
[6]	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
[7]	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
[8]	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
[9]	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.
[10]	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
[11]	J. L. Nazareth, “Computer Solution of Linear Programs,” Oxford University Press, Oxford, 1987.
[12]	V. Chvatal, “Linear Programming,” W. H. Freeman and Company, New York, 1983.
[13]	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.
[14]	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.
[15]	E. S. Badr, K. Paparrizos, N. Samaras and A. Sifaleras, “On the Basis Inverse of the Exterior Point Simplex Algorithm,” Proceedings of the 17th National Conference of Hellenic Operational Research Society (HELORS), Rio, 16-18 June 2005, pp. 677-687.
[16]	N. Ploskas, N. Samaras and K. Margaritis, “A Parallel Implementation of the Revised Simplex Algorithm Using OpenMP: Some Preliminary Results,” Optimization Theory, Decision Making, and Operational Research Applications, Springer Proceedings in Mathematics & Statistics, Vol. 31, 2013, pp. 163-175. http://dx.doi.org/10.1007/978-1-4614-5134-1_11
[17]	D. P. O’Leary and J. H. Jung, “Implementing an Interior Point Method for Linear Programs on a CPU-GPU System,” Electronic Transactions on Numerical Analysis, Vol. 28, 2008, pp. 879-899.
[18]	D. M. Gay, “Electronic Mail Distribution of Linear Programming Test Problems,” Mathematical Programming Society COAL Newsletter, Vol. 13, 1985, pp. 10-12.
[19]	D. G. Spampinato and A. C. Elster, “Linear Optimization on Modern GPUs,” Proceedings of the 23rd IEEE International Parallel and Distributed Processing Symposium, Rome, 25-29 May 2009, pp. 1-8.
[20]	CUDA-CUBLAS Library 2.0, NVIDIA Corp., 2013. http://developer.nvidia.com/object/cuda.html
[21]	LAPACK Library, 2013. http://www.cudatools.com
[22]	J. Bieling, P. Peschlow and P. Martini, “An Efficient GPU Implementation of the Revised Simplex Method,” Proceedings of the 24th IEEE International Parallel and Distributed Processing Symposium, 19-23 April 2010, Atlanta, pp. 1-8.
[23]	M. E. Lalami, V. Boyer and D. El-Baz, “Efficient Implementation of the Simplex Method on a CPU-GPU System,” Proceedings of the 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and PhD Forum, Washington DC, 16-20 May 2011, pp. 1999-2006.
[24]	X. Meyer, P. Albuquerque and B. Chopard, “A MultiGPU Implementation and Performance Model for the Standard Simplex Method,” Proceedings of the 1st International Symposium and 10th Balkan Conference on Operational Research, Thessaloniki, 22-25 September 2011, pp. 312-319.
[25]	J. Li, R. Lv, X. Hu and Z. Jiang, “A GPU-Based Parallel Algorithm for Large Scale Linear Programming Problem,” In: J. Watada, G. Phillips-Wren, L. Jai and R. J. Howlett, Eds., Intelligent Decision Technologies, SIST 10, Springer Berlin Heidelberg, Springer-Verlag, Berlin, 2011, pp. 37-46. http://dx.doi.org/10.1007/978-3-642-22194-1_4
[26]	G. B. Dantzig, A. Orden and P. Wolfe, “The Generalized Simplex Method,” RAND P-392-1, RAND Corporation, 1953.
[27]	Y. Zhang, “Solving Large-Scale Linear Programs by Interior-Point Methods Under the MATLAB Environment,” Technical Report TR96-01, Department of Mathematics and Statistics, University of Maryland, Baltimore, 1995.