Neighborhood Structures for GPU-based Local Search Algorithms

Thé Van Luong 1 Nouredine Melab 1 El-Ghazali Talbi 1
1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : Local search algorithms are powerful heuristics for solving computationally hard problems in science and industry. In these methods, designing neighborhood operators to explore large promising regions of the search space may improve the quality of the obtained solutions at the expense of a high computation process. As a consequence, the use of GPU computing provides an efficient way to speed up the search. However, designing applications on GPU is still complex and many issues have to be faced. We provide a methodology to design and implement different neighborhood structures for LS algorithms on GPU. The work has been evaluated for binary problems and the obtained results are convincing both in terms of efficiency, quality and robustness of the provided solutions at run time.
Type de document :
Article dans une revue
Parallel Processing Letters, World Scientific Publishing, 2010, 20 (4), pp.307-324
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger
Contributeur : Thé Van Luong <>
Soumis le : jeudi 23 septembre 2010 - 12:22:57
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : vendredi 24 décembre 2010 - 02:46:13


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00520461, version 1


Thé Van Luong, Nouredine Melab, El-Ghazali Talbi. Neighborhood Structures for GPU-based Local Search Algorithms. Parallel Processing Letters, World Scientific Publishing, 2010, 20 (4), pp.307-324. 〈inria-00520461〉



Consultations de la notice


Téléchargements de fichiers