| Profil | Master universitaire en informatique ou en mathématique ou en sciences de l’ingénieur |
| Prérequis | Connaissances de programmation objet (Java) et bases en fonctionnels (si possible scala) |
| Durée | min 12 semaines, ampleur du travail modulée en fonction de la durée |
Possibilité de stage de pôles (financement des déplacements)
Département: Algorithmique combinatoire ⊕
Expertises:
Algorithmique et Optimisation Combinatoire ⊕
Asset: Oscar.CBLS ⊕
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 contraintes (CP).
Le CETIC développe depuis plusieurs années une technologie d’optimisation (OscaR.cbls), qui vise à traiter efficacement des problèmes de grande taille, et à supporter une plus grande flexibilité sur la définition des problèmes à optimiser. OscaR.cbls dispose notamment d’un très bon module d’optimisation de routage de véhicules. Il est actuellement possible, par exemple, de traiter des problèmes de voyageur de commerce avec mille nœuds (destinations) quasi instantanément et avec dix mille nœuds en un temps raisonnable. OscaR est écrit en Scala, un langage multiparadigme très efficace pour programmer ce type d’applications.
Malgré sa grande efficacité, le moteur OscaR est mono-thread : sa recherche n’occupe qu’un seul coeur alors que la plupart des processeurs modernes disposes de nombreux coeurs physiques ou hyperthreadés.
L’objectif du stage est de paralléliser la recherche de solutions dans OscaR.cbls en faisant explorer différentes zones de l’espace de solutions en parallèle par plusieurs machines ou coeurs (workers), suivant un modèle maître-esclave. Les esclaves sont les moteurs de recherche, et le maître coordonne la recherche.
OscaR.cbls dispose d’un langage (DSL) pour définir des procédures de recherche [Del18]. Ce DSL est constitué de « combinateurs » permettant de combiner différentes stratégies de recherche et d’y incorporer différents comportements tels de méta-heuristiques de recuit simulé ou de GLS, gestion des solutions, critères d’arrêt, sélection de voisinages, suivi graphique de la solution, etc.
L’idée est d’étendre ce DSL d’OscaR.cbls avec quelques primitives supplémentaires permettant de spécifier une procédure de recherche distribuée. Ces primitives feraient le pont entre d’une part la formulation de la procédure de recherche et la spécification de sa parallélisation, et d’autre part, la machinerie nécessaire pour effectuer le calcul de manière distribuée/parallélisée.
La machinerie utilisée pour la parallélisation/distribution sera basée sur la librairie d’acteurs Akka, intégrée au langage Scala. Une attention particulière doit être portée à la facilité d’opération et à l’expressivité du logiciel.
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.
OscaR : https://bitbucket.org/oscarlib/oscar/wiki/Home
Scala : http://www.scala-lang.org
Akka : https://akka.io/
[Del18] Renaud De Landtsheer, Yoann Guyot, Gustavo Ospina and Christophe Ponsard, Combining Neighborhoods into Local Search Strategies, Recent Developments in Metaheuristics, 2018, Lionel Amodeo, El-Ghazali Talbi and Farouk Yalaoui, Springer, 43 - 57
Contact : Renaud De Landtsheer