Recherche locale parallèle

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.

Encadrant: 
Evripidis Bampis
Co-Encadrant: 
Eric Angel, IBISC, Evry
Référent Universitaire: 
Safia Kedad-Sidhoum
Attribué: 
No
Année: 
2 018

User login