Optimisation Combinatoire Avancée (OCAV)
- Titre :
- Optimisation Combinatoire Avancée (OCAV)
- Section :
- Optionnel
- État pour cette année :
- OPEN
- Mots clés :
- Matroïdes, fonctions sous-modulaires
- Ects :
- 2
- Responsable :
- Frédéric Meunier (ENPC ParisTech)
- Intervenants :
-
Frédéric Meunier (ENPC ParisTech)
- Prérequis :
Notions de base en programmation linéaire et en graphes
- Objectif :
Former les étudiants aux notions et outils fondamentaux de l'optimisation combinatoire théorique. Leur donner en particulier les connaissances élémentaires sur les fonctions sous-modulaires, qui jouent un rôle central en économie et en machine learning. Présenter quelques-uns des grands défis actuels de l'optimisation combinatoire (questions ouvertes, conjectures).
- Contenu / Plan :
-
Matroïdes et fonctions sous-modulaires : définitions, premières propriétés, exemples
-
Optimiser avec les matroïdes : algorithme glouton
-
Minimiser une fonction sous-modulaire (algorithme de Schrijver)
-
Sous-modularité, convexité, concavité (extension de Lovász, difficulté de la maximisation)
-
Intersection de matroïdes (théorème d'Edmonds), polymatroïdes
-
Contrôle
-
- Bibliographie :
-
-
F. Bach, Learning with submodular functions: A convex optimization perspective, Foundations and Trends in Machine Learning, 6:145--373, 2013.
-
A. Schrijver, Combinatorial Optimization, volume B, Springer, 2003.
-
- Liens :
- (aucun)
- Compétences visées :
-
Capacité à mettre en place des algorithmes avancés d'optimisation combinatoire
-
Capacité à identifier des structures exploitables dans des problèmes combinatoires
-
Compréhension de certains enjeux de l'optimisation combinatoire actuelle et de ses applications en économie et au machine learning.
-
- Modalités de contrôle :
Contrôle sur table