Détails du cours OROC-RO-MH

Approximated methods

Cette page est essentiellement destinée aux enseignants et regroupe toutes les informations nécessaires à la gestion d'un cours ENSTA.

Identité du cours

Sigle : OROC-RO-MH
Titre français : Méta-Heuristiques
Titre anglais : Approximated methods
Méta infos : modifiée le : 07/09/2016   par : mcosta   Nb de visiteurs : 391   annee : 3A      periode : 1      Rattachement/module : A      ECTS : 1.5      type : unknown     
ouvert : Oui     modif. autorisée : Oui     email auto. au responsable : Oui     à évaluer : Oui     en ligne : Non    
domaine ParisTech : 1    

Equipe pédagogique

Responsable (login) :
Professeur principal :
Professeurs participants : Thierry DEFAIX,    Maurice DIAMANTINI,    Agnès PLATEAU,   
Maitres de conférences :

Contenu

a pour prérequis : OROC-RO-PM Programmation Mathématique
Objectifs : 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 deux approches de résolution. La première propose
de résoudre de façon approchée des problèmes de grandes tailles à l’aide
de métaheuristiques, en particulier les méthodes de voisinage comme la
recherche tabou ou le recuit simulé. La présentation des méthodes s'appuiera
sur divers problèmes réels de RO.
La deuxième approche est la recherche d’une solution exacte (optimale) par
des méthodes arborescentes (branch and bound) qui utilisent souvent la
programmation linéaire et des relaxations pour le calcul de bornes.
Le cours comporte également la réalisation d’un projet incluant la
programmation d’une métaheuristique.
Mots clés : Optimisation Combinatoire, Recuit Simulé, Recherche Tabou, méthodes
arborecentes, programmatin linéaire en nombres entiers.
Objectives : Many problems of operational research are difficult, especially problems of
integer linear programming. This course presents two approaches. The first one
allow to obtain approximate solutions to big sized problems by using
metaheuristics as simulated annealing or tabu search. All the courses are
illustrated by real industrial problems. The second one is the search of an
exact (optimal) solution based on branch and bound or branch and cut.
In addition, a project including the programming of a metaheuristic will be
performed.
Keywords : Combinatorial optimization. Simulated annealing, Tabu search, branch and bound,
integer linear programming.
Supports : Polycopié des vues utilisées en cours.
Biblio : Métaheuristiques pour l'optimisation difficile - Johann Dréo, Alain
Pétrovski, Patrick Siarry, Eric Taillard. Eyrolles, 2003.
Recherche opérationnelle pour ingénieurs Dominique de Werra , Thomas M.
Liebling , Jean-François Hêche Presses Polytechniques et Universitaires
Romandes (PPUR)(Eyrolles), 2003.
Integer Programming. Lawrence Wolsey. Willey, 1998.
Contrôle : - Examen.
- Soutenance du projet.

Besoins particuliers et remarques éventuelles

Moyens :
Commentaires :

Séances

ven. 04 nov. 2016   - 13:15 à 17:00 : Cours Magistral (CM)
programme : Séance 1 Introduction. Présentation des métaheuristiques à voisinages: recuit simulé et méthode tabou. Autres types de métaheuristiques (algorithmes génétiques). Exercices. Présentation du projet.
besoin :
Intervenants : Thierry DEFAIX,
ven. 18 nov. 2016   - 13:15 à 17:00 : Bloc de Module en salle Info (MODI)
programme : Séance 2 Applications des métaheursitiques. TD/TP travail en groupe sur des mini projets. Résolution de problèmes simples (recherche de voisinages, calcul des variations de coûts).
besoin :
Intervenants : Thierry DEFAIX, Maurice DIAMANTINI,
ven. 25 nov. 2016   - 13:15 à 17:00 : Bloc de Module en salle Info (MODI)
programme : Séance 3 Travail sur le projet.
besoin :
Intervenants : Maurice DIAMANTINI,
ven. 02 déc. 2016   - 13:15 à 17:00 : Cours Magistral (CM)
programme : Séance 4 Compléments sur les structures de voisinages et sur les méthodes à population.
besoin :
Intervenants : Agnès PLATEAU,
ven. 16 déc. 2016   - 13:15 à 17:00 : Bloc de Module en salle Info (MODI)
programme : Séance 5 Exercices et application des métaheuristiques à des problématiques d’allocation de fréquences
besoin :
Intervenants : Thierry DEFAIX, Maurice DIAMANTINI,
ven. 06 janv. 2017   - 13:15 à 14:45 : Contrôle (CC)
programme : Séance 6 Contrôle/QCM
besoin :
Intervenants : Thierry DEFAIX,
ven. 06 janv. 2017   - 15:00 à 17:00 : Bloc de Module en salle Info (MODI)
programme : Séance 6 bis Soutenance du projet en salle info
besoin :
Intervenants : Thierry DEFAIX, Maurice DIAMANTINI,