Trouver des instances difficiles pour des problèmes de recherche opérationnelle : Différence entre versions
| Ligne 24 : | Ligne 24 : | ||
- Recherche d'instances classiquement utilisées dans le monde | - Recherche d'instances classiquement utilisées dans le monde | ||
| − | académique pour quantifier la vitesse et la qualité des algorithmes | + | académique pour quantifier la vitesse et la qualité des algorithmes |
| − | + | ||
- Prise en main de logiciels de résolution de PLNE | - Prise en main de logiciels de résolution de PLNE | ||
Version actuelle en date du 10 novembre 2017 à 10:20
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.
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
