Optimisation Combinatoire Avancée
Public Concerné
Notions de base en programmation linéaire et en graphes
Objectifs pédagogiques
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).
Capacité et compétences acquises
- 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.
Contenu de la formation
- 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
Description des modalités de validation
- Examen final
En alternance ou en formation continue en journée :
Merci de consulter directement le secrétariat pédagogique de votre formation pour obtenir le planning.
En formation « à la carte Hors Temps de Travail », en présentiel, à distance ou hybride :
Voir les dates, les lieux d'enseignement et les modalités d'inscription sur les sites internet des centres régionaux qui proposent cette formation.
