Descriptif
De nombreux problèmes de recherche opérationnelle sont « difficiles », en particulier les problèmes d’optimisation en variables 0-1 ou entières (PLNE). Ce cours présente les métaheuristiques, des méthodes de résolution approchée des problèmes de grandes tailles, en particulier les méthodes de voisinage comme la recherche tabou ou le recuit simulé et les méthodes par population comme les algorithmes génétiques. La présentation des méthodes s'appuiera sur divers problèmes réels de RO.
Le cours comporte également la réalisation d’un projet incluant la programmation d’une métaheuristique.
Objectifs pédagogiques
- Cours magistral : 7
- Contrôle : 2
effectifs minimal / maximal:
10/50Diplôme(s) concerné(s)
Parcours de rattachement
Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
SOD321 - Optimisation Discrète
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 :
- Soutenance du projet.
- 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é
1. CM:
Séance 1
Introduction. Présentation des métaheuristiques à voisinages: recuit simulé et méthode de recherche taboue.
Autres types de métaheuristiques. Exercices. Présentation du projet.
2. Bloc de module en salle info:
Séance 2
Applications des métaheuristiques. TD/TP travail en groupe sur des mini projets.
Résolution de problèmes simples (recherche de voisinages, calcul des variations de coûts).
3. Bloc de module en salle info:
Séance 3
Travail sur le projet.
4. CM:
Séance 4
Compléments sur les structures de voisinages et sur les méthodes à population.
5. Bloc de module en salle info:
Séance 5
Conférence Industrielle : Optimisation pour l'exploitation du réseau national de transport de gaz chez GRTgaz
6. Contrôle:
Séance 6
Contrôle/QCM
7. Bloc de module en salle info:
Séance 6 bis
Soutenance du projet en salle info