La recherche locale est une technique très utilisée en optimisation combinatoire et pour
le problème du voyageur de commerce. Rappelons qu’elle consiste à définir pour chaque
solution du problème, un ensemble de solutions dites voisines, et à itérer l’instruction
suivante tant que c’est possible : « Remplacer la solution courante par une meilleure solution
voisine ». Parmi les voisinages très utilisés pour le voyageur de commerce, on peut citer
les voisinages 2-opt et 3-opt. L’objectif de ce stage sera de mettre en œuvre une technique
de parallélisation de ces voisinages. L’idée est de fractionner la solution courante sur
plusieurs processeurs, chacun d’entre-eux exécutant en parallèle une recherche locale. Ensuite
les différents processeurs s’échangent des sommets, et exécutent de nouveau une recherche
locale, et ainsi de suite. Il s’agira de programmer cette stratégie de parallélisation et de mener
des tests sur des grandes instances. Pour être efficace, l’échange des sommets entre
processeurs doit être « optimisé » et le stage consistera également à étudier cette étape
d’un point de vue algorithmique.
Thématiques
Encadrant
Evripidis Bampis
Co-encadrant
Eric Angel, IBISC, Evry
Référent universitaire
Safia Kedad-Sidhoum
Tags
Attribué
Non
Année
2018