Optimisation combinatoire

Ects : 5
Volume horaire : 18

Description du contenu de l'enseignement :
Présenter des méthodes de résolution ainsi que l’étude de la complexité des problèmes d’optimisation combinatoire.
Modélisation de problèmes d’optimisation combinatoire (relation avec la programmation linéaire en nombres entiers).
Introduction à la théorie de la complexité : NP-complétude (définition et exemples).
Méthodes exactes : arborescentes par évaluation et séparation, programmation dynamique.
Méthodes approchées : Recherche locale, algorithme glouton.
Métaheuristiques : recuit simulé, méthode tabou, algorithme génétique.