Multi-start local search algorithms on GPU - Archive ouverte HAL Access content directly
Conference Papers Year : 2010

Multi-start local search algorithms on GPU

(1) , (1) , (1)


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).
Fichier principal
Vignette du fichier
meta10.pdf (100.01 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

inria-00520469 , version 1 (23-09-2010)


  • HAL Id : inria-00520469 , version 1


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. ⟨inria-00520469⟩
149 View
104 Download


Gmail Facebook Twitter LinkedIn More