GPU computing applied to linear and mixed-integer programming

Vincent Boyer (1) , Didier El Baz (2) , M.A. Salazar-Aguilar (3)

1 Lab-LEX - Laboratoire de recherche en droit - UR 7480
2 LAAS-CDA - Équipe Calcul Distribué et Asynchronisme
3 UANL - Universidad Autonoma de Nuevo Leon [Mexique]

Thanks to CUDA and OpenCL, Graphics Processing Units (GPUs) have recently gained considerable attention in science and engineering as accelerators for High Performance Computing (HPC). In this chapter, we show how the Operations Research (OR) community can take great benefit of GPUs. In particular, we present a survey of the main contributions to the field of GPU computing applied to linear and mixed-integer programming. The OR field is rich in complex problems and sophisticated algorithms that can take advantage of parallelization. However, all algorithms in the literature do not fit to the SIMT paradigm. Therefore, we highlight the main issues tackled by different authors to overcome the difficulties of implementation and the results obtained with their optimization algorithms via GPU computing.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Vincent Boyer, Didier El Baz, M.A. Salazar-Aguilar. GPU computing applied to linear and mixed-integer programming. Advances in GPU, Research and Practice, Elsevier, pp.247-271, 2017, 978-0-12-803738-6. ⟨10.1016/B978-0-12-803738-6.00010-0⟩. ⟨hal-02091756⟩