Trouver des instances difficiles pour des problèmes de recherche opérationnelle

De Ensiwiki
Révision de 7 novembre 2017 à 08:08 par Braunern (discussion | contributions) (Page créée avec « {{Sujet irl | labo = GScop | titre = Trouver des instances difficiles pour des problèmes de recherche opérationnelle | equipe = ROSP | encadrants = nadia.brauner@imag.fr... »)

(diff) ← Version précédente | Voir la version courante (diff) | Version suivante → (diff)
Aller à : navigation, rechercher


Trouver des instances difficiles pour des problèmes de recherche opérationnelle

Labo GScop
Equipe ROSP
Encadrants nadia.brauner@imag.fr


Sujet

Ce projet s’inscrit dans le cadre de la recherche opérationnelle. L’objectif est de construire des instances « difficiles » pour des problèmes difficiles (au sens de la complexité).

L’étudiant devra d’abord choisir un problème connu comme étant difficile en théorique (NP-complet) et en pratique (coloration, domination…). Il devra ensuite définir quel type de difficulté il souhaite étudier (instance difficile à résoudre à la main malgré sa petite taille, taille minimale des instances de problème qu’on n’arrive pas à résoudre optimalement dans un temps donné, difficulté à trouver une solution réalisable...). Il devra ensuite mettre en place un protocole d’expérimentation et d’évaluation pour proposer un générateur d’instance.

Ces instances seront utilisées dans le cadre des enseignements de l’équipe de Recherche Opérationnelle (études de cas, exercices). Elles pourront également enrichir les benchmark (collections d’instances partagées par les chercheurs et sur lesquels sont évalués les algorithmes) de la littérature.

Compétences

Recherche opérationnelle

Encadrants

Nadia Brauner Nadia.Brauner@imag.fr