Parallélisation de recherche opérationnelle sur cluster

Parallélisation de recherche opérationnelle sur cluster

Profil Etudiant niveau fin de bac ou master
Prérequis Bon programmeur, connaissance des principes de programmation distribuée et de recherche opérationnelle.
Durée Minimum 6 semaines

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

Les différents moteurs sont déjà efficaces en soi, Par exemple, le moteur CBLS permet de résoudre des problèmes de grande taille. Par exemple, le problème des "N reines" à 50000 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.

OscaR est écrit en Scala, un langage multiparadigme très efficace pour programmer ce type d’application. L’objectif du stage est de paralléliser la recherche de solution en faisant explorer différentes zones de l’espace de solution en parallèle par plusieurs machines, suivant un modèle maître-esclave. Les esclaves sont les moteurs de recherche, et le maître coordonne la recherche.

Travail à réaliser

On souhaite avoir un framework de coordination de la recherche sur un réseau de machine (cluster). La coordination doit pouvoir être programmée de manière customisée de manière à pouvoir gérer les éléments suivants :

  • La liste des « n » meilleures solutions trouvées
  • Le degré d’exploration autour de ces solutions, et la diversification que l’on souhaite voir implémentée autour de ces solutions.
  • Les différents affinages que l’on souhaite réaliser sur une solution s’ils doivent être faits sur des moteurs différents, par exemple : augmentation de la taille des voisinages sur des solutions identifiées comme « prometteuses.
  • La diversification que l’on souhaite voir implémentée par le moteur (restart)

Les esclaves proposent une interface, que le moteur de recherche doit implémenter. Cette interface devrait avoir les fonctionnalités suivantes :

  • Chercher une solution à partir de rien
  • Charger une solution donnée
  • Randomizer la solution courante du moteur, avec éventuellement une distance de randomization
  • Effectuer de la recherche, en spécifiant un nombre de pas, ou une durée limite, et éventuellement un degré pour les méta-heuristiques à appliquer (ex : requit simulé)

Le maître doit proposer une API et un DSL (Domain Specific Language) permettant de spécifier la coordination souhaitée pour la recherche.

On peut éventuellement utiliser des moteurs de type différents (ensemble de voisinages différents, ou CBLS et LNS par exemple, qui peuvent être spécifiés via le paramètre de recherche).

Tous les moteurs n’ont pas les mêmes possibilités. Par exemple, un moteur CP
peut trouver une solution initiale, un moteur CBLS peut améliorer une solution autour de contraintes fortes, etc. Ces capacités se reflètent dans les fonctionnalités offertes par l4API des moteurs. De plus, certaines machines peuvent ne proposer qu4un sous-ensemble des moteurs de recherche.

On souhaite aussi avoir un mécanisme de démarrage et d4arrêt de l4infrastructure.

Encadrement

Le travail se fera au sein de l’équipe d’algorithmique et optimisation. Une interaction sera également prévue avec certains chercheurs experts en systèmes distribués. Des interactions seront également possibles avec des chercheurs de l’UCL. Le stage a une importante connotation algorithmique sur un outil Open Source en pleine expansion. L’adéquation du profil sera validé préalablement au démarrage du stage.

Références

Contact : Renaud De Landtsheer email:rdl@cetic.be