Nature UE
Crédits ECTS 3
Volume horaire total 20
Volume horaire CM 20

Pré-requis

Programmation Linéaire – Les bases d’algèbre Linéaire – Théorie des flots.

Objectifs

L’équivalence entre un problème d’optimisation combinatoire et la programmation linéaire. L’utilité des algorithmes combinatoires des flots et de plus courts chemins pour la résolution des problèmes d’optimisation plus complexes. Analyse de l’efficacité des algorithmes de plans-coupants en se basant sur les propriétés structurelles du problème ou de la fonction objective.

Contenu

L’approche polyédrale pour les problèmes d’optimisation combinatoire et l’algorithme des plans-coupants. Illustration de l’approche sur des problèmes polynomiaux et NP-durs.

Appartient à

Informations complémentaires

L’équivalence entre un problème d’optimisation combinatoire et la programmation linéaire. L’utilité des algorithmes combinatoires des flots et de plus courts chemins pour la résolution des problèmes d’optimisation plus complexes. Analyse de l’efficacité des algorithmes de plans-coupants en se basant sur les propriétés structurelles du problème ou de la fonction objective.