Skip to Main content Skip to Navigation
Conference papers

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
Inria Lille - Nord Europe, LIFL - Laboratoire d'Informatique Fondamentale de Lille
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).
Document type :
Conference papers
Complete list of metadata

Cited literature [2 references]  Display  Hide  Download
Contributor : Thé Van Luong Connect in order to contact the contributor
Submitted on : Thursday, September 23, 2010 - 1:02:31 PM
Last modification on : Thursday, January 20, 2022 - 5:27:50 PM
Long-term archiving on: : Friday, December 24, 2010 - 2:48:32 AM


Files produced by the author(s)


  • 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⟩



Les métriques sont temporairement indisponibles