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

De Ensiwiki
Révision de 10 novembre 2017 à 10:20 par Braunern (discussion | contributions)

(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.

Tâches envisagées:

- Travail de bibliographie

- Formulations du problème en programmation linéaire en nombres entiers (PLNE)

- Recherche d'instances classiquement utilisées dans le monde académique pour quantifier la vitesse et la qualité des algorithmes

- Prise en main de logiciels de résolution de PLNE

- Résolution de ces instances par la PLNE

- Recherche des heuristiques les plus couramment utilisées

- Résolution à l'aide de ces heuristiques

- Analyse et interprétation des données numériques

L'approche proposée ci-dessus peut être enrichie suivant la créativité du groupe candidat. En particulier, d'autres approches algorithmiques peuvent être envisagées: méta-heuristiques, algorithmes de populations, nouveaux algorithmes ad-hoc faits maison...

Compétences

Un intérêt pour le Recherche Opérationnelle, ses outils et méthodes est nécéssaire.

Encadrants

Nadia Brauner Nadia.Brauner@imag.fr