Multi-start local search algorithms on GPU

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 : In practice, combinatorial optimization problems are complex and computationally time-intensive. Even if local search (LS) algorithms allow to significantly reduce the computation time cost of the solution exploration space, the use of parallelism is required to accelerate the search process. Indeed, LSs are inherently parallel and three parallel models are often used to solve efficiently large combinatorial problems: algorithmic-level (multi-start model), iteration-level (parallel evaluation of the neighborhood), and the solution-level (parallel evaluation of a single solution). The main objective of this paper is to deal with the algorithmic-level on GPU architectures where many LSs are executed in parallel. More exactly, we propose to study different schemes of deployment for the design of multi-start LSs on GPU based on popular hill climbing (HC), simulated annealing (SA) and tabu search (TS).
Type de document :
Communication dans un congrès
International Conference on Metaheuristics and Nature Inspired Computing (META), 2010, Djerba, Tunisia. 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00520469
Contributeur : Thé Van Luong <>
Soumis le : jeudi 23 septembre 2010 - 13:02:31
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : vendredi 24 décembre 2010 - 02:48:32

Fichier

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

Identifiants

  • HAL Id : inria-00520469, version 1

Citation

Thé Van Luong, Nouredine Melab, El-Ghazali Talbi. Multi-start local search algorithms on GPU. International Conference on Metaheuristics and Nature Inspired Computing (META), 2010, Djerba, Tunisia. 2010. 〈inria-00520469〉

Partager

Métriques

Consultations de la notice

312

Téléchargements de fichiers

171