Parallélisation des solveurs de contraintes

La Programmation Par Contraintes (PPC) est une approche qui consiste à trouver des solutions aux problèmes combinatoires de grande taille. Ces problèmes sont considérés très difficiles à résoudre par l'humain, comme les problèmes d'ordonnancement et de planification. Le principe de la PPC consiste dans un premier temps à modéliser les problèmes sous forme d'un ensemble de variables prenant leurs valeurs dans un ensemble fini, liées par un ensemble de contraintes. Ensuite, pour trouver des solutions, un algorithme de recherche arborescente est appliqué. Les algorithmes de recherche arborescente utilisés en PPC sont assez semblables aux algorithmes exacts utilisés par la Programmation Mathématique (PM) dans le sens où tous les deux parcourent un arbre de recherche pour trouver une solution. Actuellement, avec la disponibilité des ressources de calcul (cloud computing et data center) et les progrès réalisés dans le domaine du parallélisme (architectures, systèmes, langages, environnements d'exécution et algorithmes) de nouveaux défis sont apparus pour la conception d'outils à l'instar des solveurs de PPC. La parallélisation est donc devenue une nécessité pour répondre aux exigences de performance et pour proposer de nouvelles fonctionnalités. Cela afin d'optimiser la résolution des problèmes de satisfaction et d'optimisation de contraintes. En PPC la parallélisation est basée sur deux approches : Parallélisation de la search et la parallélisation Portfolio. La parallélisation de la search consiste à partitionner à la demande l'arbre de recherche unique généré par un seul algorithme de recherche en un ensemble de sous-arbres, pour ensuite affecter chaque sous-arbre à un cœur de calcul. En PPC, il existe plusieurs algorithmes de recherche, certains sont plus efficaces que d'autres, mais cela dépend généralement de la nature des problèmes de contraintes. Cependant la difficulté reste de choisir le bon algorithme. Pour bénéficier de la variété des algorithmes et de la disponibilité des ressources de calcul, un autre type de parallélisation est proposé, appelé Portfolio. La parallélisation Portfolio classique consiste à exécuter plusieurs algorithmes de recherche sur différents cœurs de calcul, ensuite le premier algorithme qui trouve une solution met fin à tous les autres.