APM_5OD21_TA - Optimisation discrète (3A/Master - 2024-25)

Ce cours traite des méthodes de résolution de problèmes d’optimisation combinatoire fondées sur la programmation mathématique. Après une introduction générale on montre que de nombreux problèmes de Recherche Opérationnelle peuvent être modélisés puis résolus à l’aide de la Programmation Linéaire (PL) où la fonction objectif et les contraintes sont toutes linéaires et les variables sont continues. Le cours présente les principes de base de la PL et les principaux algorithmes de résolution. L’approche par PL fournit également une aide à la résolution de problèmes plus difficiles (non linéaires, en variables entières,…) en particulier en fournissant des bornes de la solution optimale. On étudiera les méthodes de relaxations continues et lagrangiennes ainsi que l'amélioration des bornes par des méthodes de coupes. Le cours sera illustré par des applications concrètes (tournées de véhicules, localisation, ordonnancement). Enfin, on abordera la résolution de problèmes en univers incertain.
Un apprentissage à des logiciels de modélisation et de PL est proposé en TP puis approfondi dans la réalisation d’un projet.