Optimisation Combinatoire Avancée
Sessions de formation
(Fuseau horaire : Europe/Paris)
Centre Cnam Paris - Formation Annuelle en présentiel
La période de cours est planifiée du 15/09/2025 au 06/06/2026
La période d'inscription est programmée du 02/06/2025 10:00 au 17/10/2025 18:00
Présentation
Public, conditions d'accès et prérequis
Notions de base en programmation linéaire et en graphes
Objectifs
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
-
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
Modalités d'évaluation
- Examen final