Large Neighborhood Local Search Optimization on Graphics Processing Units

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 (LS) algorithms are among the most powerful techniques for solving computationally hard problems in combinatorial optimization. These algorithms could be viewed as ``walks through neighborhoods'' where the walks are performed by iterative procedures that allow to move from a solution to another one in the solution space. In these heuristics, designing operators to explore large promising regions of the search space may improve the quality of the obtained solutions at the expense of a highly computationally process. Therefore, the use of graphics processing units (GPUs) provides an efficient complementary way to speed up the search. However, designing applications on GPU is still complex and error-prone. We provide a methodology to design and implement large neighborhood LS algorithms on GPU. Finding efficient mappings of the neighborhood structures onto the GPU threads organization is a challenging issue dealt with in this paper. The work has been experimented for binary problems by deploying multiple neighborhood structures. The obtained results are convincing both in terms of efficiency, quality and robustness of the provided solutions at run time.
Type de document :
Communication dans un congrès
Workshop on Large-Scale Parallel Processing (LSPP) in Conjunction with the International Parallel & Distributed Processing Symposium (IPDPS), 2010, Atlanta, United States. 2010
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00520465
Contributeur : Thé Van Luong <>
Soumis le : jeudi 23 septembre 2010 - 12:41:18
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : jeudi 30 juin 2011 - 13:30:37

Fichier

journalGPU.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00520465, version 1

Citation

Thé Van Luong, Nouredine Melab, El-Ghazali Talbi. Large Neighborhood Local Search Optimization on Graphics Processing Units. Workshop on Large-Scale Parallel Processing (LSPP) in Conjunction with the International Parallel & Distributed Processing Symposium (IPDPS), 2010, Atlanta, United States. 2010. 〈inria-00520465〉

Partager

Métriques

Consultations de la notice

289

Téléchargements de fichiers

289