Efficient GPU-based implementations of simplex type algorithms

Nikolaos Ploskas and Nikolaos Samaras

Applied Mathematics and Computation, 2015, vol. 250, issue C, 552-570

Abstract: 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.

Keywords: Linear Programming; Simplex type algorithms; Graphical Processing Unit; Parallel Computing; MATLAB (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300314014714
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:250:y:2015:i:c:p:552-570

DOI: 10.1016/j.amc.2014.10.096

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().