Recherche Opérationnelle, Optimisation

Master 1 ISIDIS - 2014/2015

Annales

Retrouver l'année 2013-2014.

Questions ?

Contacter l'équipe enseignante

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 de problèmes et s'appuie sur des exemples pratiques.

haut

Evaluation

L'évaluation comprend :

  • 2 Projets notés, 22%,
  • 1 écrit intermédiaire, 11%, le 24/10/2014 de 30 minutes.
  • 1 écrit terminal, 67%, entre le 17 et le 19 décembre 2014 de 2h (à préciser).

Enoncé du projet 2 zip.
A rendre avant le dimanche 14/12/2014 minuit.

Enoncé du projet 1 zip rendu le vendredi 16/11/2014.

Oral projet 1

Les présentations en personne ont lieu le :
  • Vendredi 21 novembre 2014 entre 10h30 à 12h00 (cf. ordre de passage).
L'ordre de passage est donné par cette liste.

Vous êtes nombreux, il n'est pas possible de prendre du retard. Le temps est décompté de la manière suivante :
  • 1 minute pour le changement et l'installation
  • 5 minutes de présentation
  • 1 minute de question
Je vous indiquerai lorsqu'il vous restera plus qu'une minute de présentation.

Pour votre présentation qui devra se faire sous forme de présentation électronique.

Vous trouverez de nombreux conseils trés utiles sur le web pour réussir cette épreuve. La grille d'évaluation est disponible ici pour vous guider.


Cette UE compte pour 5 crédits ECTS.

Les énoncés des devoirs de l'année passée : ici.

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

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

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
annexe
td tp
02 Algorithmes de recherche locale (1) cours td tp cor
03 Algorithmes de recherche locale (2) cours td td tp
04 Algorithmes évolutionnaires cours td tp cor
05 Stratégies d'évolution cours part1 part2 cor
06 Modélisation en prog. linéaire cours td
07 Programmation Linéaire (2) cours td tp
08 Simplexe cours td tp cor

haut

Bibliographie

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

haut

Horaires

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


Consulter l'emploi du master : edt

haut

dernière modification : 18 septembre 2014