Trouver des instances difficiles pour des problèmes de recherche opérationnelle : Différence entre versions

De Ensiwiki
Aller à : navigation, rechercher
 
(Une révision intermédiaire par le même utilisateur non affichée)
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 de
+
académique pour quantifier la vitesse et la qualité des algorithmes  
coloration
+
  
 
- Prise en main de logiciels de résolution de PLNE
 
- Prise en main de logiciels de résolution de PLNE
Ligne 44 : Ligne 43 :
 
=== Compétences ===
 
=== Compétences ===
  
Recherche opérationnelle
+
Un intérêt pour le Recherche Opérationnelle, ses outils et méthodes est nécéssaire.
  
 
=== Encadrants ===
 
=== Encadrants ===
  
 
Nadia Brauner Nadia.Brauner@imag.fr
 
Nadia Brauner Nadia.Brauner@imag.fr

Version actuelle en date du 10 novembre 2017 à 10:20


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