Optimisation Combinatoire
Ce cours concerne la L3 de l'UCO (Université Catholique de l'Ouest).
On s'intéresse à l'Optimisation Combinatoire du point de vue de l'informatique avec utilisation d'heuristiques et métaheuristiques.
L'Optimisation Combinatoire, (sous-ensemble à nombre de solutions finies de l'optimisation discrète), est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité.
Nous traitons ici essentiellement d'optimisation sur des variables à domaines de valeur discrets, souvent finis c'est à dire le problème de satisfiabilité d'une expression booléenne (SAT), les problèmes de satisfaction de contraintes (CSP).
Le plan du cours est le suivant :
- Chapitre 1 : Complexité : notation, classes de problèmes P, NP
- Chapitre 2 : Le problème SAT : satisaisabilité d'un ensemble de clauses en calcul propositionnel
- Chapitre 3 : L'Optimisation Combinatoire : méthode exactes et inexactes (Recherche Locale, Tabu, Recuit Simulé, Algorithmes Génétiques)
- Chapitre 4 : Le solveur Minizinc
- Chapitre 5 : Problème du voyageur de commerce
- Chapitre 6 : Problème du sac à dos
Projet de programmation :
- 2020-2021 Problème des Pigeons