Thèse au LINA

Nous recherchons un excellent candidat pour une thèse dans l’équipe TASC (contraintes) du LINA (Université de Nantes, UMR 6241), commençant en septembre 2013.

Titre : Nouveaux algorithmes parallèles d’optimisation combinatoire
Encadrants : Éric Monfroy et Florian Richoux
Financement : Allocation de recherche du MESR
Possibilités d’enseigner à travers un monitorat.

Résumé du sujet :
L’évolution de l’architecture des ordinateurs est telle que l’ordinateur commun de demain sera massivement multi-cœurs, disposant de plusieurs milliers d’unités de calcul. Or, nous ne savons pas aujourd’hui concevoir des algorithmes tirant efficacement partie de cette puissance. Ceci est vrai en particulier pour les algorithmes d’optimisation combinatoire, comme les algorithmes de résolution de problème de contraintes. Il existe plusieurs techniques pour résoudre les problèmes de contraintes : la programmation par contrainte, la programmation linéaire, les méthodes de satisfaction booléenne et les méthodes de recherche locale pour donner une liste non-exhaustive. Ces dernières sont bien souvent parmi les techniques les plus efficaces pour résoudre les problèmes de grande taille. De nos jours et à notre connaissance, il n’existe qu’un seul algorithme (Adaptive Search, un algorithme de recherche locale) ayant de très bonnes performances passant à l’échelle des milliers de cœurs. Toutefois le schéma parallèle de cet algorithme ne comprend pas de système de communications coopérantes inter-processus. De plus, la montée en puissance d’algorithmes de plus en plus complexes entraîne un nombre de paramètres qui est devenu intraitable manuellement, et les algorithmes parallèles ne font qu’accentuer la tendance.

Dans ce contexte, cette thèse se voit assigner deux objectifs majeurs :
- Proposer et implémenter des méthodes scalables de recherche locale sur plusieurs milliers de cœurs avec des processus communiquants et coopérants. Derrière cet objectif s’en cache un autre : dé finir une approche portfolio , consistant à avoir simultanément des processus de nature différentes (c’est-à- dire différents algorithmes, ou encore le même algorithme avec différents paramètres) explorant l’espace de recherche.
- Développer et implémenter des mécanismes d’auto-tuning pour les algorithmes de recherche locale, c’est-à-dire des mécanismes permettant d’automatiser le paramétrage (à travers des méthodes d’apprentissage), et les inclure dans les méthodes de recherche locale parallèles proposées pendant la thèse.

Mots clés : Problèmes de contraintes, algorithmes parallèles de recherche locale, architectures massivement parallèle, auto-tuning, méthodes d’apprentissage.

Le sujet complet peut être téléchargé à l’adresse suivante : http://pagesperso.lina.univ-nantes.fr/~richoux-f/sujets/parallel_PhD-fr.pdf

Pour déposer votre candidature, merci de nous envoyer un dossier complet au adresses suivantes : eric.monfroy@univ-nantes.fr et florian.richoux@univ-nantes.fr
N’hésitez pas à nous contacter pour de plus amples informations.