Contactez-nous

Optimisation Combinatoire Avancée

Mis à jour le

Responsable(s) : Mme Safia KEDAD SIDHOUM

  • Cours
Code Cnam : US336B

Envie d'en savoir plus sur cette formation ?

Afin d’obtenir les tarifs, le calendrier de la formation, en distanciel, en présentiel, le lieu de la formation et un contact, remplissez les critères suivants :

Afficher le centre adapté à mes besoins

Afin d’obtenir les tarifs, le calendrier de la formation et le lieu de la formation, remplissez les critères suivants :

  • Durée : 22 heures
  • Package
  • 2 crédits

Présentation

Public, conditions d'accès et prérequis

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

Compétences et débouchés

Compétences

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

Parcours

Informations pratiques

Contact

Programme

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