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.

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.