Métaheuristiques et Optimisation Combinatoire

L'équipe "Métaheuristiques et Optimisation combinatoire" s'intéresse à la résolution de problèmes combinatoires de grande taille sous contraintes complexes. L'équipe se spécialise dans les méthodes heuristiques modernes dites métaheuristiques. Les principales métaheuristiques étudiées sont les suivantes : 1) recherche locale avancée (méthode tabou, recuit simulé...), 2) approche évolutionniste : (algorithme génétique...) et 3) approche hybride (génétique et recherche locale, recherche locale et simplexe).

D'une manière générale, le travail de l'équipe s'organise autour de deux thèmes étroitement liés. Le premier thème vise à développer des algorithmes performants fondés sur les métaheuristiques pour résoudre des problèmes difficiles. A ce titre, nous travaillons sur des problèmes généraux NP-difficiles comme la coloration de graphes, le sac-à-dos multidimensionnel, et la satisfaction de contraintes (CSP et MCSP). Nous travaillons également sur des applications réelles comme, par exemple, l'affectation de fréquences et le positionnement d'antennes dans les réseaux radio-mobiles, l'affectation et le routage de longueurs d'ondes dans les réseaux optiques SDH/WDM, et la planification journalière de prises de vue de SPOT 5, ceci dans le cadre de projets de collaboration au niveau national ou européen.

Le deuxième thème concerne les problèmes fondamentaux liés à la caractérisation de la difficulté des problèmes combinatoires ainsi que la compréhension de comportements des algorithmes heuristiques. Nous travaillons sur la technique de "densité d'état" pour étudier la distribution des configurations dans l'espace des configurations d'une instance donnée. Nous proposons des mesures fondées sur cette distribution pour étudier différents "paysages" (de recherche et de processus). On s'interesse également à la distribution des optima locaux et à différentes corrélations entre les configurations visitées par un algorithme heuristique.

L'équipe est impliquée dans plusieurs projets de R&D européens, nationaux ou industriels (ESPRIT 4, RNRT, CNET-FT...c.f. "Contrats de R&D" du LERIA). L'équipe participe également à des groupes de travail nationaux et européens (EvoNet, PRC/GDR-I3, ALP...).

Composition de l'équipe

    Jin-Kao Hao, Professeur

Membres permanents :

    Jean-Michel Richer, Maître de Conférences

    Frédéric Saubion, Maître de Conférences

ATER / Post-doctorant :

    Manuel Clergue

    Mériéma Bélaidouni

Doctorants :

    Vincent Barichard, Alain Chabier (ILOG), Hervé Deleau, Jean-Philippe Hamiez, Hakim Mybed (France Telecom), Nicolas Pech-Gourg

Anciens doctorants :

    Raphaël Dorne (Research Scientist au British Telecom's Advanced Communications Technology Centre, Suffolk, U.K.)
    Philippe Galinier (Research Fellow à l'Ecole Polytechnique de Montréal, Canada)
    Michel Vasquez (Enseignant-chercheur à l'Ecole des Mines d'Alès, site EERIE Nîmes)