PROGRAMME DE L’UNITE D’ENSEIGNEMENT :
Dans ce cours, nous explorons différents outils de résolution pour des problèmes d'optimisation combinatoire. Les méthodes considérées permettront d'envisager à la fois des résolutions exactes et approchées de ces problèmes. Nous nous interrogerons également sur la meilleure façon de modéliser certains problèmes connus de recherche opérationnelle.
Dans un premier temps, la modélisation de problème à l'aide de programmes linéaires sera considérée. On proposera des résolutions graphiques de tels programmes, ou avec l'aide de la dualité, ou encore le développement d’algorithmes de Branch and Bound et de programmation dynamique. Par la suite, nous verrons que certains problèmes classiques de RO peuvent se modéliser sur des graphes, comme les problèmes de flot ou d'ordonnancement. Pour ces questions, des algorithmes exacts et approchés seront présentés. On s'interrogera notamment sur les garanties d'optimalité de certaines heuristiques. Enfin, nous verrons comment résoudre de façon approchée certains des problèmes les plus difficiles, à l'aide de metaheuristiques basées sur des méthodes de population (algorithmes génétiques) et de voisinage (méthode tabou, recuit simulé).
