Description

• 
  

  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

  
  

Finalité

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).

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.

  
  

Public

Notions de base en programmation linéaire et en graphes