US336B

Optimisation Combinatoire Avancée


2 crédits Safia KEDAD SIDHOUM EPN05 - Informatique Unité spécifique de type cours

Publié Du 01-09-2024 au 31-08-9999

Prérequis

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

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.

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 de validation

  • Examen final

Thésaurus du Cnam :

  • Aucune indexation

Thésaurus Formacode :

  • Aucune indexation

Secrétariat

Libellé
Recherche opérationnelle
Nom du contact
Adresses email
secretariat.ro@cnam.fr
Numéros de téléphone
01 40 27 22 67
Adresse postale
2D4P20, 33-1-10, 2 rue Conté
Paris 75003