Optimisation combinatoire avancée : Matroïdes et fonctions sous-modulaires

Enseignant : Frédéric Meunier

Prérequis : Notions de théorie des graphes, algèbre et programmation linéaire

Objectif : Les matroïdes sont un des outils fondamentaux de l'optimisation combinatoire. Les fonctions sous-modulaires forment un sujet connexe, également fondamental en optimisation combinatoire, avec des applications dépassant largement ce domaine (machine learning, économie, etc.).

Le plan du cours est le suivant :

Définition des matroïdes.
Notions de bases, circuits, rangs.
Problème de la base de poids maximal et algorithme glouton.
Problème de l'intersection de matroïdes.
Définition des fonctions sous-modulaires et des polymatroïdes.
Optimisation sur un polymatroïde.
Minimisation d'une fonction sous-modulaire.
Intersection de polymatroïdes.

Quelques notes de cours :

Notes sur les matroïdes et les fonctions sous-modulaires.

Quelques exercices :

Exercices sur les matroïdes.
Exercices sur les fonctions sous-modulaires.

Examens passés :

Bibliographie :

F. Bach, Learning with submodular functions: A convex optimization perspective, Foundations and Trends in Machine Learning, 6:145--373, 2013.
B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, Volume B, Springer, 2008.
A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003.