v2.11.0 (5687)

Cours scientifiques - APM_5OD21_TA : Optimisation discrète

Domaine > Applied Maths.

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.

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/50

Diplô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 20

Littérale/grade européen

Pour 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
L'UE est acquise si Note finale >= 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
L'UE est acquise si Note finale >= 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

Mots clés

Optimisation combinatoire, programmation linéaire, relaxation lagrangienne, génération de colonnes, décomposition

Méthodes pédagogiques

Cours, Exercices et Travaux Pratiques
Veuillez patienter