Yannick Ngoko - Optimiser la coopération entre plusieurs heuristiques résolvant le même problème

Sur de nombreux problèmes combinatoires comme SAT ou CSP, on peut facilement trouver, étant donné un sous ensemble d’heuristiques, un sous ensemble d’instances du problème sur lequel aucune heuristique ne domine complètement les autres (sur le temps d’exécution). D’où l’intérêt de définir des modèles d’exécutions coopératifs entre plusieurs heuristiques résolvant un problème. Dans ce séminaire nous nous intéressons à l’exécution concurrente de plusieurs heuristiques dans les schémas de portfolio d’algorithmes. Ces modèles ont l’avantage d’être applicable sur une large classe de problèmes. En outre leur efficacité a déjà été démontré sur plusieurs cas pratiques. Toutefois, il reste difficile étant donné un ensemble d’heuristiques de déterminer la meilleure exécution basée sur les portfolio.

Dans cet exposé, nous nous intéressons à cette problématique en contexte parallèle et homogène. Notre exposé comporte deux grandes parties. Dans la première partie, nous présentons la formulation originale Sayag et al. pour la construction des portfolio d’algorithmes. Dans notre contexte, celle ci débouche sur un problème combinatoire NP-complet et inapproximable. Pour le résoudre, nous proposons une décomposition du problème de construction de portfolio en deux sous problèmes : Un problème de couvertures d’ensemble et un problème d’équilibrage de charges. Le premier problème est résolu par une heuristique inspirée de la résolution du Max Set Cover et le second, via programmation dynamique.

Dans la seconde partie du séminaire, nous proposons une implémentation multi-threadée permettant de construire des portfolio sur les machines à mémoire partagées. Les expérimentations sont faites sur le problème de satisfactions de Contraintes (CSP). Les implémentations proposées posent de nombreuses questions que nous considérons en discussion. D’un point de vue pratique, nous avons notamment la question de limiter les interférences entre différents threads ainsi que celle de synchroniser rapidement leur arrêt (dès qu’un thread a une solution). D’un point de vue théorique, il s’agit de formuler une solution efficace dans le modèle de Sayag et al. dans un contexte à information partielle.

A la fin de ce séminaire, je ferai aussi un court résumé de mes travaux de recherche sur la prédiction des QoS des compositions de services.