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

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...).