TITLE:
A Computational Comparison of Basis Updating Schemes for the Simplex Algorithm on a CPU-GPU System
AUTHORS:
Nikolaos Ploskas, Nikolaos Samaras
KEYWORDS:
Simplex Algorithm; Basis Inverse; Graphics Processing Unit; MATLAB; Compute Unified Device Architecture
JOURNAL NAME:
American Journal of Operations Research,
Vol.3 No.6,
October
28,
2013
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.