Optimisation combinatoire

Apprendre les principes et mettre en œuvre les techniques d’optimisation combinatoire.

― Connaître la théorie de la complexité.
― Savoir distinguer un problème difficile d’un problème facile au sens de cette théorie.
― Être capable de formuler un problème d’optimisation combinatoire comme un problème de décision.
― Être capable de construire plusieurs versions relaxées d’un problème d’optimisation combinatoire.
― Savoir implémenter un algorithme glouton.
― Être capable d’implémenter un algorithme de recherche par séparation et évaluation (branch-and-bound), connaître les leviers de l’efficacité de ces méthodes.
― Savoir résoudre des problèmes divers (sac à dos en variables binaires, problèmes d’ordonnancement à une machine, programmes linéaires en variables entières) à l’aide d’un algorithme de recherche par séparation et évaluation.
― Avoir compris le principe d’optimalité de Bellman.
― Savoir formuler un problème d’optimisation combinatoire de manière récursive quand c’est possible et mettre en œuvre un algorithme de programmation dynamique.