Proposition de thèse         

Utilisation de grilles de calculs pervasives pour la résolution de problèmes d’optimisation combinatoire

                                                                                 

Financement : allocation de recherche (contrat doctoral du Ministère Enseignement Supérieur & Recherche).

Laboratoire : Centre de Recherche en Informatique (CRI) de l’Université Paris 1 (Panthéon-Sorbonne)

Mots clés : Optimisation Combinatoire, CSP, SAT, Contraintes, grilles de calcul, Informatique pervasive

Description 

Le but de cette thèse est d’explorer les opportunités qu’offrent les grilles pervasives pour résoudre les problèmes d’optimisation combinatoires en parallèle. Ces problèmes apparaissent naturellement dans l’industrie (planification, d'ordonnancement, découpe, validation,...). Pour résoudre ces problèmes très difficiles plusieurs techniques existent telles que : la Programmation par Contraintes, les méthodes de satisfaction booléenne (SAT), les metaheuristiques (notamment la Recherche Locale). Toutefois, le caractère exponentiel des problèmes abordés, nécessite rapidement de très fortes puissances de calcul pour attaquer des instances de taille supérieure. La simplification d’accès aux grilles de calcul (grid computing) permet d’envisager leur utilisation dans le monde industriel, y compris les PME. Les grilles de calcul peuvent fournir une telle puissance, en permettant de distribuer les calculs. Ces plates-formes de calcul sont caractérisées par l’agrégation de différents noeuds de calcul sous la forme de clusters (ou grappes). Ces nœuds de calcul (souvent multiprocesseurs et/ou multicoeurs) sont indépendants vis-à-vis de leur mémoire vive et doivent reposer sur des réseaux de communication performants afin de s’organiser et de gérer les tâches de calcul. L’exploitation efficace de ces grilles est un enjeu majeur comme en témoignent les efforts de promotion et de déploiement de Google pour son paradigme de calculs distribués MapReduce. Il se trouve que l’utilisation des grilles pour les problèmes d’optimisation combinatoire est un terrain de recherche quasiment vierge (donc à explorer). L’étape suivante consiste à prendre en compte l’aspect volatile des grilles pervasives (desktop grids). La topologie d’une grille pervasive est naturellement dynamique, avec des nœuds qui rejoignent la grille, d’autres qui se déconnectent, des noeuds qui présentent des problèmes de communication ou d’autres qui deviennent trop chargés,... Des capacités d’adaptation au contexte et de résilience deviennent nécessaires pour que ces grilles puissent tirer profit de cet environnement dynamique. Il s’agit donc d’inventer des algorithmes de résolution parallèles capables de s’adapter à ces environnements à géométrie variable.

 

Profil des candidats

Le candidat devra être titulaire d’un Master Recherche en Informatique (ou diplôme équivalent). Il devra posséder un très bon niveau en programmation (C, C++, Java) y compris dans les couches basses (ex: gestion des processus). Des compétences en programmation parallèle sont un atout significatif (ex: MPI). De même qu’une connaissance des techniques de résolutions des problèmes à contraintes. Le candidat doit avoir de très bonnes qualités rédactionnelles en français et en anglais. Il doit être très motivé, autonome, avoir l’esprit d’initiative avec une réelle capacité à s’organiser et suivre un planning.

Pour candidater : envoyer un CV détaillé, une lettre de motivation, vos notes de Master et Licence et des lettres de recommandations à Daniel Diaz (daniel.diaz@univ-paris1.fr) tel: +33 1 44 07 89 61

Date limite de candidature : 1er juillet 2012

Pour plus d’Informations cliquez sur ce lien  et/ou contactez Daniel Diaz