Descriptif
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.
Un apprentissage à des logiciels de modélisation et de PL est proposé en TP puis approfondi dans la réalisation d’un projet.
Objectifs pédagogiques
Connaissance des aspects théoriques et pratiques de la programmation en nombres entiers et de sa capacité de modélisation et de résolution de problèmes d'optimisation Combinatoire. Savoir-faire pour la résolution pratique de problèmes de grande taille par des méthodes de décomposition.
21 heures en présentiel (6 blocs ou créneaux)
effectifs minimal / maximal:
10/50Diplôme(s) concerné(s)
Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
RO201- Initiation à la Recherche Opérationnelle
Format des notes
Numérique sur 20Littérale/grade européenPour les étudiants du diplôme Inside ENSTA Paris
Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)- le rattrapage est obligatoire si :
- Note initiale < 6
- le rattrapage peut être demandé par l'étudiant si :
- 6 ≤ note initiale < 10
- Crédits ECTS acquis : 1.5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
L'UE est évaluée par les étudiants.
Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
Vos modalités d'acquisition :
Examen et soutenance du projet.
Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)- le rattrapage est obligatoire si :
- Note initiale < 6
- le rattrapage peut être demandé par l'étudiant si :
- 6 ≤ note initiale < 10
- Crédits ECTS acquis : 2 ECTS
- Scientifique acquis : 2
Le coefficient de l'UE est : 1
La note obtenue rentre dans le calcul de votre GPA.
L'UE est évaluée par les étudiants.
Programme détaillé
- Séance 1: Rappels de programmation linéaire et dualité, Résolution des Programmes Linéaires en nombres entiers par l'algorithme branch and bound, mise en oeuvre grâce à l'algorithme dual du simplexe. Exercices
- Séance 2 : Aspects polyédriques de la Programmation Linéaire en Nombres Entiers : inégalités valides, algorithmes de plans coupants. Exercices. Prise en main des aspects informatiques. Présentation du projet
- Séance 3: Modélisation des problèmes par la programmation linéaire en nombres entiers, notion de bonne formulation
- Séance 4: Méthoes de décomposition, Relaxation lagrangienne, génération de colonnes. Exercices
- Séance 5: Décomposition de Benders. Point sur le projet
- Séance 6: Contrôle écrit. Soutenance de projet