×

zbMATH — the first resource for mathematics

Efficient GPU-based implementations of simplex type algorithms. (English) Zbl 1328.90003
Summary: Recent hardware advances have made it possible to solve large scale Linear Programming problems in a short amount of time. Graphical Processing Units (GPUs) have gained a lot of popularity and have been applied to linear programming algorithms. In this paper, we propose two efficient GPU-based implementations of the Revised Simplex Algorithm and a Primal-Dual Exterior Point Simplex Algorithm. Both parallel algorithms have been implemented in MATLAB using MATLAB’s Parallel Computing Toolbox. Computational results on randomly generated optimal sparse and dense linear programming problems and on a set of benchmark problems (netlib, kennington, Mészáros) are also presented. The results show that the proposed GPU implementations outperform MATLAB’s interior point method.

MSC:
90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
90C05 Linear programming
65K05 Numerical mathematical programming methods
65Y05 Parallel numerical computation
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Badr, E. S.; Moussa, M.; Papparrizos, K.; Samaras, N.; Sifaleras, A., Some computational results on MPI parallel implementations of dense simplex method, Trans. Eng. Comput. Technol., 17, 228-231, (2006)
[2] Benhamadou, M., On the simplex algorithm ‘revised form’, Adv. Eng. Software, 33, 769-777, (2002)
[3] J. Bieling, P. Peschlow, P. Martini, An efficient GPU implementation of the revised Simplex method, in: Proceedings of the 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2010), Atlanta, USA, 2010.
[4] Bixby, R. E.; Martin, A., Parallelizing the dual simplex method, Inf. J. Comput., 12, 1, 45-56, (2000) · Zbl 1034.90008
[5] Borgwardt, H. K., The average number of pivot steps required by the simplex method is polynomial, Zeit. Oper. Res., 26, 1, 157-177, (1982) · Zbl 0488.90047
[6] Cvetanovic, Z.; Freedman, E.; Nofsinger, C., Efficient decomposition and performance of parallel PDE, FFT, Monte Carlo simulations, simplex, and sparse solvers, J. Supercomput., 5, 219-238, (1991) · Zbl 0749.65100
[7] Dantzig, G. B.; Orchard-Hays, W., The product form of the inverse in the simplex method, Math. Comput., 8, 64-67, (1954) · Zbl 0055.35103
[8] Dantzig, G. B., Linear programming and extensions, (1963), Princeton University Press Princeton, NJ · Zbl 0108.33103
[9] Eckstein, J.; Boduroglu, I. I.; Polymenakos, L. C.; Goldfarb, D., Data-parallel implementations of dense simplex methods on the connection matching CM-2, ORSA J. Comput., 7, 4, 402-416, (1995) · Zbl 0842.90080
[10] N.F. Gade-Nielsen, J.B. Jorgensen, B. Dammann, MPC toolbox with GPU accelerated optimization algorithms, in: Proceedings of the 10th European Workshop on Advanced Control and Diagnosis (ACD 2012), Copenhagen, Denmark, 2012.
[11] Gay, D. M., Electronic mail distribution of linear programming test problems, Math. Progr. Soc. COAL Newslett., 13, 10-12, (1985)
[12] Goldfarb, D.; Reid, J. K., A practicable steepest-edge simplex algorithm, Math. Prog., 12, 3, 361-371, (1977) · Zbl 0443.90058
[13] Hall, J. A.J.; McKinnon, K. I.M., PARSMI, a parallel revised simplex algorithm incorporating minor iterations and devex pricing, (Wasniewski, J.; Dongarra, J.; Madsen, K.; Olesen, D., Applied Parallel Computing, Lecture Notes in Computer Science, vol. 1184, (1996), Springer), 67-76
[14] Hall, J. A.J.; McKinnon, K. I.M., ASYNPLEX, an asynchronous parallel revised simplex algorithm, Ann. Oper. Res., 81, 27-49, (1998) · Zbl 0906.90119
[15] Hall, J. A.J., Towards a practical parallelisation of the simplex method, Comput. Manage. Sci., 7, 2, 139-170, (2010) · Zbl 1185.90149
[16] Ho, J.; Sundarraj, R., On the efficacy of distributed simplex algorithms for linear programming, Comput. Optim. Appl., 3, 349-363, (1994) · Zbl 0814.90078
[17] F. Homm, N. Kaempchen, J. Ota, D. Burschka, Efficient occupancy grid computation on the GPU with lidar and radar for road boundary detection, in: Proceedings of the Intelligent Vehicles Symposium (IV), Michigan, USA, 2010, pp. 1006-1013.
[18] Jung, J. H.; O’Leary, D. P., Implementing an interior point method for linear programs on a CPU-GPU system, Electron. Trans. Numer. Anal., 28, 174189, (2008)
[19] Klee, V.; Minty, G. J., How Good is the Simplex Algorithm?, Inequalities, vol. III, (1972), Academic Press New York, pp. 159-175
[20] M.E. Lalami, V. Boyer, D. El-Baz, Efficient implementation of the simplex method on a CPU-GPU system, in: Proceedings of the 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and PhD Forum (IPDPSW 2011), Washington, USA, 2011, pp. 1999-2006.
[21] M.E. Lalami, D. El-Baz, V. Boyer, Multi GPU implementation of the simplex algorithm, in: Proceedings of the 2011 IEEE 13th International Conference on High Performance Computing and Communications (HPCC), Banff, Canada, 2011, pp. 179-186.
[22] Lentini, M.; Reinoza, A.; Teruel, A.; Guillen, A., SIMPAR: a parallel sparse simplex, Comput. Appl. Math., 14, 1, 49-58, (1995) · Zbl 0833.65052
[23] Li, J.; Lv, R.; Hu, X.; Jiang, Z., A GPU-based parallel algorithm for large scale linear programming problem, (Watada, J.; Phillips-Wren, G.; Jai, L.; Howlett, R. J., Intelligent Decision Technologies, SIST 10, (2011), Springer-Verlag Berlin, Heidelberg), 37-46
[24] Maros, I.; Khaliq, M. H., Advances in design and implementation of optimization software, Eur. J. Oper. Res., 140, 2, 322-337, (1999) · Zbl 1001.90004
[25] MATLAB’S parallel computing toolbox. <http://www.mathworks.com/products/parallel-computing/> (accessed 10.11.2013).
[26] X. Meyer, P. Albuquerque, B. Chopard, A multi-GPU implementation and performance model for the standard simplex method, in: Proceedings of the 1st International Symposium and 10th Balkan Conference on Operational Research, Thessaloniki, Greece, 2011, pp. 312-319.
[27] Nvidia, CUDA. <https://developer.nvidia.com/category/zone/cuda-zone> (accessed 10.11.2013).
[28] NVIDIA CUDA-CUBLAS Library 2.0, NVIDIA Corp. <http://developer.nvidia.com/object/cuda.html> (accessed 10.11.2013).
[29] LAPACK Library. <http://www.cudatools.com> (accessed 10.11.2013)
[30] Paparrizos, K., An infeasible exterior point simplex algorithm for assignment problems, Math. Prog., 51, 1-3, 45-54, (1991) · Zbl 0734.90055
[31] Paparrizos, K.; Samaras, N.; Stephanides, G., An efficient simplex type algorithm for sparse and dense linear programs, Eur. J. Oper. Res., 148, 2, 323-334, (2003) · Zbl 1035.90041
[32] Paparrizos, K.; Samaras, N.; Stephanides, G., A new efficient primal dual simplex algorithm, Comput. Oper. Res., 30, 9, 1383-1399, (2003) · Zbl 1031.90011
[33] Ploskas, N., Samaras, N.: Basis Update on simplex type algorithms. In: Proceedings of the EWG-DSS Thessaloniki 2013, Thessaloniki, Greece, 11 (2013). · Zbl 1328.90003
[34] Ploskas, N.; Samaras, N.; Margaritis, K., 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, 31, 163-175, (2013) · Zbl 1375.90215
[35] Ploskas, N., Samaras, N.: The impact of scaling on simplex type algorithms. In: Proceedings of the 6th Balkan Conference in Informatics, Thessaloniki, Greece, 17-22 (2013).
[36] Ploskas, N., Samaras, N.: A Computational Comparison of Scaling Techniques for Linear Optimization Problems on a GPU. International Journal of Computer Mathematics, accepted for publication. · Zbl 1308.65096
[37] Ploskas, N.; Samaras, N., A computational comparison of basis updating schemes for the simplex algorithm on a CPU-GPU system, Am. J. Oper. Res., 3, 497-505, (2013)
[38] Ploskas, N., Samaras, N.: GPU Accelerated Pivoting Rules for the Simplex Algorithm. J. Syst. Software 96, 1-9, submitted for publication. · Zbl 06704721
[39] Samaras, N.: Computational improvements and efficient implementation of two path pivoting algorithms. Ph.D. dissertation, Department of Applied Informatics, University of Macedonia (2001).
[40] Shu, W., Parallel implementation of a sparse simplex algorithm on MIMD distributed memory computers, J. Parallel Distrib. Comput., 31, 1, 25-40, (1995)
[41] Smith, E., Gondzio, J., Hall, J.: GPU acceleration of the matrix-free interior point method. In: Parallel Processing and Applied Mathematics, 681-689, Springer, Berlin Heidelberg (2012).
[42] Spampinato, D.G., Elster, A.C.: Linear optimization on modern GPUs. In: Proceedings of the 23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS 2009), Rome, Italy (2009).
[43] Stunkel, C.B., Reed, D.A.: Hypercube implementation of the simplex algorithm. In: Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, 2, 1473-1482, New York, USA, (1988).
[44] The Khronos OpenCL Working Group: OpenCL - The open standard for parallel programming of heterogeneous systems. <http://www.khronos.org/opencl/> (accessed 5.8.2013).
[45] M.E. Thomadakis, J.C. Liu, An efficient steepest-edge simplex algorithm for SIMD computers, in: Proceedings od the 10th International Conference on Supercomputing (ICS 1996), Philadelphia, Pennsylvania, USA, 1996, pp. 286-293.
[46] Tomlin, J. A., On scaling linear programming problems, Math. Program. Stud., 4, 146-166, (1975) · Zbl 0359.90050
[47] Yarmish, G.; Slyke, R., A distributed, scaleable simplex method, J. Supercomput., 49, 373-381, (2009)
[48] E.Z. Zhang, Y. Jiang, Z. Guo, X. Shen, Streamlining GPU applications on the fly: thread divergence elimination through runtime thread-data remapping, in: Proceedings of the 24th ACM International Conference on Supercomputing, Tsukuba, Japan, 2010, pp. 115-126.
[49] Zhang, Y., Solving large-scale linear programs by interior-point methods under the MATLAB environment, Optim. Methods Softw., 10, 1, 1-31, (1998) · Zbl 0916.90208
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.