Description
Cet ECUE aborde les techniques de base en programmation mathématique en nombres entiers avec différentes applications en théorie des graphes. L’étudiant est capable, à la fin de cet enseignement, de modéliser un problème en nombres entiers et connait des techniques permettant d’en trouver une solution optimale. Il est également capable d’utiliser un logiciel dédié pour résoudre un problème de ce type. Finalement, l’étudiant aura approfondi ses connaissances en théorie des graphes en abordant des classes de problèmes classiques et leurs applications.
Contenu :
- Programmation linéaire en nombres entiers : modélisation, optimalité, relaxations et bornes
- Méthodes de résolution (séparation-évaluation, séparation-coupes, programmation dynamique)
- Plus court chemin
- Flot maximum, flot à coût minimum
- Couplage, parcours Eulérien et Hamiltonien