Optimisation Combinatoire Avancée
3 ECTS - 25% Cours - 42% TD - 33% TPs
Parcours-types : IA&RF, D&C, SIAME (?)
Objectifs
Introduire les modèles et algorithmes utilisés pour résoudre des
problèmes d'optimisation combinatoire difficile comme on en rencontre dans
des domaines variés, allant de la gestion et l'utilisation efficace de
resources pour améliorer la productivité ou l'élaboration de réseaux de
communications, à, entre autres, la théorie des graphes ou l'intelligence
artificielle.
Prérequis
Notions fondamentales d'algorithmique et de théorie des graphes
Contenu
- Retour sur la programmation linéaire en nombres entiers, programmation
par contraintes, SAT
- Les classes NP et NPO, NP-complétude ; application à la cryptographie
- Méthodes de recherche arborescente complètes et incomplètes
- Approximation des solutions optimales de problèmes NP-conplets
- Travaux pratiques :
- Modélisation et résolution d'un problème de taille industrielle à
l'aide d'un outil de PLNE et/ou d'un outil de programmation par
contraintes
- Codage d'un algorithme de recherche arborescente
Bibliographie
- Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh V. Vazirani:
Algorithms. McGraw-Hill 2008
- Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial
Optimization: Algorithms and Complexity Prentice-Hall 1982
- M. R. Garey, David S. Johnson: Computers and Intractability: A Guide
to the Theory of NP-Completeness. W. H. Freeman 1979
- Handbook of Constraint Programming, Edited by Francesca Rossi,
Peter van Beek, and Toby Walsh, Elsevier, 2006.
- Krzysztof R. Apt: Principles of constraint programming. Cambridge
University Press 2003
- Juraj Hromkovic: Algorithmics for Hard Problems - Introduction to
Combinatorial Optimization, Randomization, Approximation, and
Heuristics, Second Edition Springer 2004
Compétences
- Savoir modéliser un problème d'optimisation combinatoire - 1 ECTS
- Savoir reconnaître un problème NP-difficile - 1 ECTS
- Connaître les principaux outils d'optimisation combinatoire - 1 ECTS
Mots-clefs
Optimisation combinatoire, théorie de la complexité, programmation en
nombres entiers, programmation par contraintes