Implémentation de pruning de type CP pour l’optimisation par recherche locale

Implémentation de pruning de type CP pour l’optimisation par recherche locale

Profil Etudiant en fin de master en informatique (TFE possible)
Prérequis Bon programmeur (OO et si possible connaissance en programmation fonctionnelle), connaissances en algorithmique, connaissance basique de la programmation par contrainte et de la recherche locale
Durée min 10 semaines, ampleur du travail modulée en fonction de la durée

Contexte

OscaR est un toolkit Open Source de recherche opérationnelle. Il comprend notamment un moteur de type recherche locale basée sur des contraintes (CBLS) et un moteur de programmation par contrainte (CP). OscaR est écrit en Scala, un langage multi-paradigme très efficace pour programmer ce type d’application.
Les différents moteurs sont déjà efficaces en sois. Par exemple, le moteur CBLS permet de résoudre des problèmes de grande taille. Par exemple, le problème des "N reines" à 50.000 reines peut être résolu en une grosse vingtaine de seconde, et des problèmes de scheduling de plusieurs centaines de tâches peuvent être traités efficacement.

L’objectif du stage est d’enrichir le moteur de recherche locale en le dotant d’un mécanisme inspiré de ce qu’un moteur de programmation par contrainte est capable de faire en terme de "pruning" des domaines des variables contraintes. Ce mécanisme permettrait d’accélérer considérablement les calculs, notamment dans le cadre d’applications de routage de véhicules.

Travail à réaliser

Le moteur CBLS dispose déjà d’un système de contrainte. Celui-ci ne peut actuellement qu’évaluer les contraintes pour savoir si il y a une violation ou pas. Le travail consisterait à lui ajouter deux méthodes permettant d’obtenir, pour une variable donnée, l’ensemble des valeurs admises pour cette variable par les contraintes (ou une sur-approximation serrée de cet ensemble), en considérant soit que les autres variables ne changeront pas de valeur, soit que les autres variables pourraient changer de valeur.
Un exemple d’utilisation de ce mécanisme devra être produit, dans le contexte de l’optimisation du routage de véhicule. Un environnement d’optimisation de routage est déjà disponible dans le moteur CBLS de OscaR, et l’exemple sera réalisé en utilisant cet environnement.

Encadrement

Tout le travail sera encadré, mais nécessitera un minimum d’autonomie. Il s’agit d’un stage à forte connotation algorithmique, sur un outil Open Source en pleine expansion.

Références

OscaR : https://bitbucket.org/oscarlib/oscar/wiki/Home
Scala : http://www.scala-lang.org

Contact : Renaud De Landtsheer