Recherche Opérationnelle, Optimisation

But

S'initier à la démarche de modélisation d'un problème pour le résoudre de manière informatique.
Cet enseignement présente de nombreuses méthodes de résolution et s'appuie sur des exemples pratiques.

haut

Équipe d'enseignants

Sébastien Verel

Pour contacter un des intervenants : contacts. Vous pouvez contacter l'équipe pour tout ce qui concerne cet enseignement et votre orientation.

haut

Evaluation

Deuxième projet (attention update le 18/11/2013) sur le docking (code) à rendre le dimanche 08/12/2013 avant 23h59.


Premier projet à rendre le 20/10/2013 avant 23h59.
Ecrit intermédiaire (sur feuille sans machine, 45 min.) le 15/10/2013. Aucun document autorisé.


L'évaluation comprend :

• 2 projets notés,
• 1 écrit intermédiaire,
• 1 écrit terminal, le lundi 16 décembre de 13h30 à 16h30.

La note finale est calculée comme indiqué dans le guide des études.

Cette UE compte pour 5 crédits ECTS.

Enoncé de l'écrit intermédiaire du 15/10/2013 pdf.
Enoncé de l'examen terminal pdf.

haut

Objectifs

Ils sont mis à jour régulièrement :

1. Savoir définir un problème d'optimisation combinatoire
2. Connaitre des exemples de problème d'optimisation (maxSAT, TSP, QAP, knapsack, etc.)
3. Savoir modéliser un problème en un problème d'optimisation.
4. Connaitre le principe d'une recherche locale à solution unique.
5. Connaitre la recherche aléatoire
6. Savoir comparer statistiquement deux algorithmes de recherche stochastiques.
7. Savoir définir une marche aléatoire
8. Connaitre les heuristiques "Hill-Climbing"
9. Connaitre la notion d'optimum local
10. Connaitre le dilemme exploration / exploitation
11. Savoir définir les métaheuristiques classiques (recuit simulé, recherche taboue, iterated local search)
12. Savoir définir les principes des algorithmes évolutionnaires
13. Connaitre les différents types d'algorithmes évolutionnaires
14. Savoir coder dans un langage les algorithmes d'optimisation précédents
15. Savoir définir un problème d'optimisation numérique
16. Connaitre les algorithmes de stratégie d'évolution : (1+1) et (mu/mu,lambda)
17. Connaitre l'influence du step-size (sigma) dans ces algorithmes
18. Connaitre le principe du réglage du step-size à l'aide de la rêgle du 1/5 success rule.
19. Savoir coder dans un langage les algorithmes de stratégies d'évolution précédents
20. Savoir modéliser en problème de programmation linéaire un problème simple
21. Connaitre les formes normales et standard d'un problème de programmation linéaire
22. Savoir coder sous AMPL un problème de programmation linéaire
23. Connaitre les notions de polyèdre et de polytope
24. Savoir résoudre géométrique un problème de programmation linéaire
25. Savoir résoudre à l'aide de l'algorithme du simplexe un problème de programmation linéaire
26. Savoir trouver une base de solutions admissibles pour l'algorithme du simplexe

haut

Supports de Cours et de TP

Voici l'ensemble des supports de cours et des émoncés des TP.

Séance	Titre	cours	TD	TP
01	Intro. pb. optimisation / modélisation	cours	td	tp
02	Algorithmes de recherche locale (1)	cours	td	tp cor
03	Algorithmes de recherche locale (2)	cours	td	tp code rapport prés.
04	Algorithmes évolutionnaires	cours	td	tp cor
05	Stratégies d'évolution	cours	td	tp
06	Modélisation en prog. linéaire	cours	td
07	Programmation Linéaire (2)	cours	td	tp
08	Simplexe	cours	td	tp

haut

Bibliographie

Quelques repères biblio- /webo- graphiques qui vont se complèter au fur et à mesure :

• Métaheuristiques pour l'optimisation difficile, Johann Dréo, Alain Pétrowski, Patrick Siarry, Eric Taillard, 2003.
• Aide mémoire R, Aymeric Duclert, 2011.
• Comment rédiger un rapport ou une publication scientique., Alexandre Buttler, Université de France-Comté, 2002.

haut

Horaires

12h de CM, 12h de TD, et 15h de TP.


Consulter l'emploi du master : edt

haut