A GPU-based Iterated Tabu Search for Solving ...
Type de document :
Communication dans un congrès avec actes
Titre :
A GPU-based Iterated Tabu Search for Solving the Quadratic 3-dimensional Assignment Problem
Auteur(s) :
Luong, Thé Van [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Melab, Nouredine [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Talbi, El-Ghazali [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Melab, Nouredine [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Talbi, El-Ghazali [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Titre de la manifestation scientifique :
Workshop on Parallel Optimization in Emerging Computing Environments (POECE) in Conjunction with the International Conference on Computer Systems and Applications (AICCSA)
Ville :
Hammamet
Pays :
Tunisie
Date de début de la manifestation scientifique :
2010
Date de publication :
2010
Discipline(s) HAL :
Informatique [cs]/Autre [cs.OH]
Résumé en anglais : [en]
The quadratic 3-dimensional assignment problem (Q3AP) is an extension of the well-known NP-hard quadratic assignment problem. It has been proved to be one of the most difficult combinatorial optimization problems. Local ...
Lire la suite >The quadratic 3-dimensional assignment problem (Q3AP) is an extension of the well-known NP-hard quadratic assignment problem. It has been proved to be one of the most difficult combinatorial optimization problems. Local search (LS) algorithms are a class of heuristics which have been successfully applied to solve such hard optimization problem. These methods handle with a single solution iteratively improved by exploring its neighborhood in the solution space. In this paper, we propose an iterated tabu search for solving the Q3AP. The design of this algorithm is essentially based on a new large neighborhood structure. Indeed, in LS heuristics, designing operators to explore large promising regions of the search space may improve the quality of the obtained solutions. However, designing such neighborhood is 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. The proposed GPU-based iterated tabu search has been experimented on 5 different Q3AP instances. The obtained results are convincing both in terms of efficiency, quality and robustness of the provided solutions at run time.Lire moins >
Lire la suite >The quadratic 3-dimensional assignment problem (Q3AP) is an extension of the well-known NP-hard quadratic assignment problem. It has been proved to be one of the most difficult combinatorial optimization problems. Local search (LS) algorithms are a class of heuristics which have been successfully applied to solve such hard optimization problem. These methods handle with a single solution iteratively improved by exploring its neighborhood in the solution space. In this paper, we propose an iterated tabu search for solving the Q3AP. The design of this algorithm is essentially based on a new large neighborhood structure. Indeed, in LS heuristics, designing operators to explore large promising regions of the search space may improve the quality of the obtained solutions. However, designing such neighborhood is 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. The proposed GPU-based iterated tabu search has been experimented on 5 different Q3AP instances. The obtained results are convincing both in terms of efficiency, quality and robustness of the provided solutions at run time.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.inria.fr/inria-00520468/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/inria-00520468/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- POECE2010Paper.pdf
- Accès libre
- Accéder au document