Méthodes d'apprentissage appliquées aux heuristiques de recherche pour les problèmes de satisfaction de contraintes

Motivation : La programmation par contraintes (PPC) propose un cadre formel pour représenter et résoudre des problèmes combinatoires concrets tels que la conception d'horaires de personnel d'hôpital ou l'allocation des portes d'embarquement dans un aéroport. Un problème de satisfaction de contraintes se modélise à l'aide de relations logiques, ou contraintes, entre des variables. La résolution du problème revient alors à identifier une solution qui respecte ces contraintes. Même si l'utilisation de techniques d'inférence puissantes, comme les algorithmes de filtrage, permettent de réduire sensiblement l'espace des solutions, cela reste insuffisant. Il convient alors de guider la recherche à l'aide d'heuristiques. Enjeux et Contexte théorique : Cambazard et Jussien (2005) justifient l'intérêt porté aux heuristiques de recherche en les qualifiant de « Saint Graal » à la fois des communautés de recherche opérationnelle (RO) et de programmation par contraintes (PPC). Parmi les meilleures heuristiques actuelles figurent Impact-Based Search (IBS – Refalo (2004)), qui utilise la réduction de domaine après branchement, et maxSD (Zanarini et Pesant, 2007}), qui utilise le dénombrement des solutions des contraintes. D'autres heuristiques se basent quant à elles sur une estimation de la distribution de solutions, comme les méthodes Belief-Propagation (BP – Kschischang et al.(2001}) et Survey-Propagation (SP – Mezard et al. 2002). Ces méthodes, dites d'inférence, se sont notamment distinguées pour la résolution de problèmes de satisfaction booléenne. Récemment, une variante de ces deux méthodes, dénommée Expectation-Maximization Belief-Propagation, a été proposée par Hsu et al. (2007). Enfin, ces méthodes d'inférence permettent également de déterminer certaines caractéristiques de la structure du problème que l'on cherche à résoudre. À titre d'exemple, de telles estimations permettent ainsi d'identifier les variables dites backbones (Kilby et al. (2005)), qui sont les variables qui prennent toujours la même valeur quelle que soit la solution. Ainsi, une estimation de la distribution des solutions ne fournit pas seulement de l'information utile pour une heuristique, mais également de l'information sur la structure sous-tendante du problème.