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




A Computational Comparison of Basis Updating Schemes for the Simplex Algorithm on a CPU-GPU System - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

The computation of the basis inverse is the most time-consuming stepin simplex type algorithms. This inverse does not have to be computed fromscratch at any iteration, but updating schemes can be applied to acceleratethis calculation. In this paper, we perform a computational comparison in whichthe basis inverse is computed with five different updating schemes. Then, wepropose a parallel implementation of two updating schemes on a CPU-GPU Systemusing MATLAB and CUDA environment. Finally, a computational study on randomlygenerated full dense linear programs is preented toestablish the practical value of GPU-based implementation.

KEYWORDS

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

Cite this paper

N. Ploskas and N. Samaras -A Computational Comparison of Basis Updating Schemes for the Simplex Algorithm on a CPU-GPU System,- American Journal of Operations Research, Vol. 3 No. 6, 2013, pp. 497-505. doi: 10.4236-ajor.2013.36048.





Autor: Nikolaos Ploskas, Nikolaos Samaras

Fuente: http://www.scirp.org/



DESCARGAR PDF




Documentos relacionados