A multi-GPU implementation and performance model for the standard simplex method

Meyer, Xavier (School of Engineering, Architecture and Landscape (hepia), HES-SO // University of Applied Sciences Western Switzerland) ; Albuquerque, Paul (School of Engineering, Architecture and Landscape (hepia), HES-SO // University of Applied Sciences Western Switzerland) ; Chopard, Bastien (University of Geneva, Geneva, Switzerland)

The standard simplex method is a well-known optimization algorithm for solving linear programming models in operations research. It is part of software often employed by businesses for solving scheduling or assignment problems. But their always increasing complexity and size drives the demand for more computational power. In the past few years, GPUs have gained a lot of popularity as they offer an opportunity to accelerate many algorithms. In this paper we present a mono and a multi-GPU implementation of the standard simplex method, which is based on CUDA. Measurements show that it outperforms the CLP solver on large enough problems. We also derive a performance model and establish its accurateness. To our knowledge, only the revised simplex method has so far been implemented on a GPU.


Conference Type:
full paper
Faculty:
Ingénierie et Architecture
School:
HEPIA - Genève
Institute:
inIT - Institut d'Ingénierie Informatique et des Télécommunications
Publisher:
Thessaloniki, Greece, 22-25 September 2011
Date:
2011-09
Thessaloniki, Greece
22-25 September 2011
Pagination:
8 p.
Published in:
Proceedings of the 1st International Symposium and 10th Balkan Conference on Operational Research (BALCOR 2011), 22-25 September 2011, Thessaloniki, Greece
Appears in Collection:



 Record created 2020-06-26, last modified 2020-07-03

Fulltext:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)