Trouver des instances difficiles pour des problèmes de recherche opérationnelle
Sommaire
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
