Partager cette page :

Métaheuristiques pour l’optimisation combinatoire à grande échelle

le 5 novembre 2013

de 15h30 à 17h00

ENS Rennes Salle du conseil
Plan d'accès

Intervention de Jin Kao-Hao (LERIA, Université d'Angers). Séminaire du département Informatique et télécommunications.

L'optimisation combinatoire vise à déterminer parmi un ensemble fini de solutions potentielles une solution particulière qui satisfait un critère de minimisation ou maximisation. L'optimisation combinatoire est réputée pour être difficile dans le cas général (problèmes NP-hard). En plus des méthodes classiques de résolution exacte, la résolution approchée s'est émergée depuis une vingtaine d'année comme une alternative pour vaincre la complexité intrinsèque des problèmes combinatoires. Dans cet exposé, nous proposons d'abord un survol des méthodes approchées dites métaheuristiques. Nous présentons ensuite quelques exemples d'application sur des problèmes NP-difficiles bien connus (coloration de graphes, sac-à-dos multidimensionnel, clique maximum...) et des cas réels (planification de fréquences et positionnement d'antennes dans les réseaux radio-mobiles, planification de prises de vues de satellite, planification de rencontres sportives...).
Thématique(s)
Formation, Recherche - Valorisation
Contact
François Schwarzentruber

Mise à jour le 9 septembre 2019