Skip to main content
SpringerLink
Log in

Revised simplex algorithm for linear programming on GPUs with CUDA

  • Published:
Multimedia Tools and Applications Aims and scope Submit manuscript

Abstract

The revised simplex algorithm (RSA) is a typical algorithm for solving linear programming problems. Many theoretical modifications have been done to make the algorithm more efficient, but almost all of them were based on single-instruction single-data architecture processors (CPUs), which could not make full use of the inherent parallel characteristics of RSAs. We propose a novel single-instruction multiple-data architecture processor (GPU) based on the RSA in this paper. The intensive matrix manipulations of a traditional RSA are offloaded to the GPU, which helps to make full use of its powerful parallel processing ability. We implemented the GPU-based RSA on compute unified device architecture (CUDA). Numerical experiments on randomly generated linear programs show that the GPU-based RSA can not only find the correct optimal solutions, but can also reach a speed of up to 100 times as fast as that of a CPU-based RSA: it also runs 3 to 11 times as fast as MATLAB.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

  1. Anderson JA, Lorenz CD, Travesset A (2008) General purpose molecular dynamics simulations fully implemented on graphics processing units. J Comput Phys 227(10):5342–5359

    Article  Google Scholar 

  2. Belleman RG, Bédorf J, Zwart SFP (2008) High performance direct gravitational N-body simulations on graphics processing units II: an implementation in CUDA. New Astron 13(2):103–112

    Article  Google Scholar 

  3. Belloch JA, Gonzalez A, Vidal AM, Cobos M (2015) On the performance of multi-GPU-based expert systems for acoustic localization involving massive microphone arrays. Expert Syst Appl 42(13):5607–5620

    Article  Google Scholar 

  4. Demirel E, Demirel N, Gökçen H (2016) A mixed integer linear programming model to optimize reverse logistics activities of end-of-life vehicles in Turkey. J Clean Prod 112:2101–2113

    Article  Google Scholar 

  5. Douglas CC, Lee L, Yeung MC (2016) Hierarchical density-based clustering based on GPU accelerated data indexing strategy. Procedia Comput Sci 80:951–961

    Article  Google Scholar 

  6. Ezzati R, Khorram E, Enayati R (2015) A new algorithm to solve fully fuzzy linear programming problems using the MOLP problem. Appl Math Model 39(12):3183–3193

    Article  MathSciNet  Google Scholar 

  7. Fu Z, Ren K, Shu J, et al. (2015) Enabling personalized search over encrypted outsourced data with efficiency improvement

  8. Gobron S, Devillard F, Heit B (2007) Retina simulation using cellular automata and GPU programming. Mach Vis Appl 18(6):331–342

    Article  Google Scholar 

  9. Guastaroba G, Mansini R, Ogryczak W, Speranza MG (2016) Linear programming models based on omega ratio for the enhanced index tracking problem. Eur J Oper Res 251(3):938–956

    Article  MathSciNet  Google Scholar 

  10. Ho TY, Lam PM, Leung CS (2008) Parallelization of cellular neural networks on GPU. Pattern Recogn 41(8):2684–2692

    Article  Google Scholar 

  11. Huangfu Q, Hall JAJ (2015) Novel update techniques for the revised simplex method. Comput Optim Appl 60(3):587–608

    Article  MathSciNet  Google Scholar 

  12. Jermain CL, Rowlands GE, Buhrman RA, Ralph DC (2016) GPU-accelerated micromagnetic simulations using cloud computing. J Magn Magn Mater 401:320–322

    Article  Google Scholar 

  13. Junior HV, Lins MPE (2005) An improved initial basis for the simplex algorithm. Comput Oper Res 32(8):1983–1993

    Article  MathSciNet  Google Scholar 

  14. Leung CS, Wong TT, Lam PM et al (2006) An RBF-based compression method for image-based relighting. IEEE Trans Image Process 15(4):1031–1041

    Article  Google Scholar 

  15. Liu W, Schmidt B, Voss G et al (2007) Streaming algorithms for biological sequence alignment on GPUs. IEEE Trans Parallel Distrib Syst 18(9):1270–1281

    Article  Google Scholar 

  16. Liu W, Schmidt B, Voss G, et al. (2007) Molecular dynamics simulations on commodity GPUs with CUDA//International Conference on High-Performance Computing. Springer Berlin Heidelberg 185–196

  17. Luh H, Tsaih R (2002) An efficient search direction for linear programming problems. Comput Oper Res 29(2):195–203

    Article  MathSciNet  Google Scholar 

  18. Marziale L, Richard GG, Roussev V (2007) Massive threading: using GPUs to increase the performance of digital forensics tools. Digit Investig 4:73–81

    Article  Google Scholar 

  19. Oh KS, Jung K (2004) GPU implementation of neural networks. Pattern Recogn 37(6):1311–1314

    Article  Google Scholar 

  20. Owens JD, Luebke D, Govindaraju N et al (2007) A survey of general-purpose computation on graphics hardware //computer graphics forum. Blackwell Publishing Ltd 26(1):80–113

    Google Scholar 

  21. Paparrizos K, Samaras N, Stephanides G (2003) A new efficient primal dual simplex algorithm. Comput Oper Res 30(9):1383–1399

    Article  MathSciNet  Google Scholar 

  22. Peercy M, Segal M, Gerstmann D. (2006) A performance-oriented data parallel virtual machine for GPUs//ACM SIGGRAPH 2006 Sketches. ACM. 184

  23. Richter C, Schöps S, Clemens M. (2016) Multi-GPU Acceleration of Algebraic Multigrid Preconditioners//Scientific Computing in Electrical Engineering. Springer International Publishing. 83–90

  24. Rocha P, Rodrigues R, Gomes A M, et al. (2015) GPU-Based Computing for Nesting Problems: The Importance of Sequences in Static Selection Approaches//Operations Research and Big Data. Springer International Publishing 195–202

  25. Sanders J, Kandrot E. (2010) CUDA by example: an introduction to general-purpose GPU programming. Addison-Wesley Professional

  26. URL: http://docs.nvidia.com/cuda/optimus-developer-guide/index.html, 2017

  27. Xia Z, Wang X, Sun X, Wang Q (2016) A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data. IEEE Trans Parallel Distrib Syst 27(2):340–352

    Article  Google Scholar 

  28. Yang X, Pi X, Zeng L, et al. (2005) GPU-based real-time simulation and rendering of unbounded ocean surface//Ninth International Conference on Computer Aided Design and Computer Graphics (CAD-CG'05). IEEE. 6 pp

  29. Zhangjie F, Xingming S, Qi L et al (2015) Achieving efficient cloud search services: multi-keyword ranked search over encrypted cloud data supporting parallel computing. IEICE Trans Commun 98(1):190–200

    Google Scholar 

  30. Zhong Z, Feng M, Liu D (2015) Parallelization of revised simplex algorithm on GPUs //network and information Systems for Computers (ICNISC), 2015 international conference on. IEEE. 349–353

Download references

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (51679105, 61672261,51409117), Jilin Province Department of Education Thirteen Five science and technology research projects [2016] No. 432, [2017] No.JJKH20170804KJ.

Author information

Authors and Affiliations

  1. College of Computer Science and Technology, Jilin University, Changchun, 130012, China

    Lili He, Hongtao Bai, Yu Jiang, Dantong Ouyang & Shanshan Jiang

  2. Center for Computer Fundamental Education, Jilin University, Changchun, 130012, China

    Hongtao Bai

  3. Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun, 130012, China

    Lili He, Hongtao Bai, Yu Jiang, Dantong Ouyang & Shanshan Jiang

Authors
  1. Lili He
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hongtao Bai
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yu Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Dantong Ouyang
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Shanshan Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Hongtao Bai, Yu Jiang or Dantong Ouyang.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

He, L., Bai, H., Jiang, Y. et al. Revised simplex algorithm for linear programming on GPUs with CUDA. Multimed Tools Appl 77, 30035–30050 (2018). https://doi.org/10.1007/s11042-018-5947-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11042-018-5947-z

Keywords

Search

Navigation