Efficient Implementation of the Simplex Method on a CPU-GPU System
CNRS, LAAS, Toulouse, France
IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011
@inproceedings{lalami2011efficient,
title={Efficient implementation of the simplex method on a CPU-GPU system},
author={Lalami, M. and Boyer, V. and El Baz, D.},
booktitle={25th symposium IEEE IPDPSW, Anchorage, USA},
year={2011}
}
The Simplex algorithm is a well known method to solve linear programming (LP) problems. In this paper, we propose a parallel implementation of the Simplex on a CPU-GPU systems via CUDA. Double precision implementation is used in order to improve the quality of solutions. Computational tests have been carried out on randomly generated instances for non-sparse LP problems. The tests show a maximum speedup of 12:5 on a GTX 260 board.
November 14, 2011 by hgpu
