Logo ESI
Bannière
ESI talents

Bienvenue



Retour - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Syllabus OPT
Télécharger



Crédits : 3

OPT
Optimisation Combinatoire
Combinatorial optimization

Coef : 3
VH Cours : 22.50
VH TD : 22.50
Pré-requis :
Structure de données, THP, ROP1

Ingénierie des Compétences

Familles de Compétences
  • CF6 : Concevoir des systèmes orientés données et/ou d'aide à la décision
Type de compétence: TEC : Technique, MET : Méthodologique, MOD : Modélisation, OPE : Opérationnel,
Niveau de compétence:
Base Intermédiaire Avancé


Famille de Compétence Compétence Elément de Compétence Type
CF6 C6.4: Analyser et exploiter des méthodes de résolution de problèmes combinatoires C64.1: Analyser des méthodes de résolution des problèmes d’optimisation combinatoire MET
C64.2: Expérimenter différentes méthodes d'optimisation pour résoudre des problèmes combinatoires TEC

Description du programme de la matière

Objectifs:

L’optimisation combinatoire joue un rôle fondamental en recherche opérationnelle, en mathématiques discrète et en informatique. Les domaines d’application de l’optimisation combinatoire sont multiples et variés tels que, l’ingénierie,  la télécommunication, les transports ou les sciences sociales. Bien que les problèmes d’optimisation combinatoires soient faciles à formuler, ils sont en général difficiles à résoudre. Cette difficulté est liée au temps d’exécution nécessaire à la résolution de ce problème. En effet, le fait qu’un algorithme arrive à atteindre sa fin d’exécution n’est pas d’un grand intérêt sur le plan opérationnel si son temps d’exécution est très grand. Ce cours vise donc à
Etudier les méthodes de résolution des problèmes d’optimisation combinatoire en allant des méthodes exactes vers les méthodes approchées,
Montrer l’applicabilité effective des méthodes présentées à des problèmes pratiques.
Se rendre compte des limites de chaque famille de méthodes d’optimisation et de leur dépendance des différents paramètres en entrée, d’où la nécessité de proposer de nouveaux paradigmes (méthodes hybrides, parallèles, hyper-heuristiques, apprentissage automatique)

Contenu:

I. Introduction à l’optimisation combinatoire
1. La problématique de l’optimisation combinatoire
2. Outils fondamentaux de l’optimisation combinatoire
3. Quelques modèles de l’optimisation combinatoire
Problème de tournée
Problème de coloration des graphes
Problème d’ordonnancement
Problème de Gestion des stocks
II. Méthodes par séparation et évaluation
1. Principe de l’approche par séparation et évaluation (Branch and Bound)
2. Application aux problèmes à la programmation linéaire en nombres entiers
3. Application au problème du sac à dos
4. Application au problème voyageur de commerce
III. Programmation dynamique
1. Exemple introductif : Problème de gestion de stock
2. Résolution du problème de gestion des stocks en utilisant les réseaux (algorithme de Bellman)
3. Principes fondamentaux de la programmation dynamique: Problèmes justifiables par la programmation dynamique.
4. Application la programmation dynamique aux problème d’optimisation combinatoire

IV. Méthodes Approchées
1. Heuristiques Gloutonnes
2. Méthodes spécifiques de construction
3. Méthodes de voisinage
Méthode du Recuit simulé
Recherche Tabou
4. Métaheuristiques évolutionnaires :
Algorithmes Génétiques,
Colonies de fourmis, …

V. Vers de nouvelles approches de résolution
Approches hybrides et parallèles : Exemples
Hyper-heuristiques
Approches avec apprentissage automatique

Travail Personnel:

1 projet sous forme de TP présentiel (Le projet est évalué sous la base de deux livrables, une présentation et une application . Le TP est compté au même titre qu’ un contrôle)

Bibliographie:

R. Diestel, « Graph Theory », Springer, Second Edition, 1999
B. Korte, J. Vygen, « Combinatorial Optimisation », Springer,2001.
P. Lacomme, C. Prins, M. Sevaux, « Algorithmes De Graphes », Eyrolles, 2003.
G. Nemhauser, « Introduction to Dynamic Programming », Wiley, 1966.
P. Van Hentenryck and L. Michel. Constraint-based Local Search. MIT Press, 2005. G.L. Nemhauser and L.A. Wolsey. Integer and Combinatorial Optimization. John Wiley & Sons, 1988.
DRÉO, Johann, et al. Métaheuristiques pour l'optimisation difficile. Eyrolles, 2003.‏
CHARON, Irène; GERMA, Anne; HUDRY, Olivier. Méthodes d'optimisation combinatoire. Paris: Masson, 1996.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -