Composante
École Nationale Supérieure d'Électrotechnique d'Électronique d'Informatique d'Hydraulique et des Télécommunications
Objectifs
- Comprendre les concepts fondamentaux et spécificités de l’optimisation combinatoire (notions de complexité, explosion combinatoire, etc.)
- Identifier et modéliser des problématiques de différents domaines ou cahiers des charges sous forme de problèmes d'optimisation combinatoire
- Résoudre des problèmes combinatoires à l'aide de méthodes arborescentes exactes (branch-and-bound) pour garantir l'optimalité des solutions obtenues
- Concevoir des méthodes approchées de type métaheuristiques (algorithmes génétiques, recherche taboue, ...) pour générer des solutions adaptées au contexte, sans garantie d'optimalité mais en temps d'exécution limité
- Implémenter les algorithmes proposés et évaluer leurs performances sur des études de cas issues de différents domaines: informatique, logistique, productique, etc.
Description
Ce cours s'intéresse à la modélisation et la résolution approchée ou exacte de problèmes de décision et d’optimisation combinatoire NP-difficiles rencontrés dans différents domaines.
Pré-requis obligatoires
programmation linéaire