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

Resume Motivation : La programmation par contraintes (PPC) propose un cadre formel pour representer et resoudre des problemes combinatoires concrets tels que la conception d'horaires de personnel d'hopital ou l'allocation des portes d'embarquement dans un aeroport. Un probleme de satisfaction de contraintes se modelise a l'aide de relations logiques, ou contraintes, entre des variables. La resolution du probleme revient alors a identifier une solution qui respecte ces contraintes. Meme si l'utilisation de techniques d'inference puissantes, comme les algorithmes de filtrage, permettent de reduire sensiblement l'espace des solutions, cela reste insuffisant. Il convient alors de guider la recherche a l'aide d'heuristiques. Enjeux et Contexte theorique : Cambazard et Jussien (2005) justifient l'interet porte aux heuristiques de recherche en les qualifiant de « Saint Graal » a la fois des communautes de recherche operationnelle (RO) et de programmation par contraintes (PPC). Parmi les meilleures heuristiques actuelles figurent Impact-Based Search (IBS – Refalo (2004)), qui utilise la reduction de domaine apres branchement, et maxSD (Zanarini et Pesant, 2007}), qui utilise le denombrement des solutions des contraintes. D'autres heuristiques se basent quant a elles sur une estimation de la distribution de solutions, comme les methodes Belief-Propagation (BP – Kschischang et al.(2001}) et Survey-Propagation (SP – Mezard et al. 2002). Ces methodes, dites d'inference, se sont notamment distinguees pour la resolution de problemes de satisfaction booleenne. Recemment, une variante de ces deux methodes, denommee Expectation-Maximization Belief-Propagation, a ete proposee par Hsu et al. (2007). Enfin, ces methodes d'inference permettent egalement de determiner certaines caracteristiques de la structure du probleme que l'on cherche a resoudre. A 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 meme 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 egalement de l'information sur la structure sous-tendante du probleme. ----------Abstract Motivation Constraint Programming (CP) is a paradigm to model and solve pratical combinatorial problems, such as nurse scheduling or airport gate assignment. CP models such problems as Constraint Satisfaction Problems (CSPs), i.e. a set of relations between variables. Solving a CSP then becomes equivalent to finding a solution that satisfies all relations. Although strong inference techniques such as filtering algorithms lead to a much smaller solution space, the solution space typically remains too large to be explored exhaustively. This is where search heuristics come in and guide the search toward promising areas. Significance and Theoritical Background Cambazard and Jussien (2005) emphasize the importance of search heuristics when they refer to them as the Holy Grail of both Operations Research (OR) and Constraint Programming (CP) communities. Two of the best current search heuristics are Impact-Based Search (IBS - Refalo (2004)) which exploits domain reduction, and Zanarini and Pesant (2007), which exploits constraint-based solution counting. Other heuristics are designed to estimate the distribution of solutions, such as Belief-Propagation (BP - Kschischang et al. (2001)) and Survey-Propagation (SP - Mezard et al. (2002)). These inference methods have been particularly suitable to Satisfiability (SAT) problems. Recently, Hsu et al. proposed Expectation-Maximization Belief-Propagation (EMBP), a variation of these two methods. In addition, these inference methods also provide information about the underlying structure of the problem. For example, such estimates enable to detect backbone variables (Kilby et al. (2005), i.e. that always take the same value regardless of the solution. As a result, these estimates not only direct the search but also provide structural information about the solution space.