Methodes d'apprentissage appliquees aux heuristiques de recherche pour les problemes de satisfaction de contraintes

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.;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.;Purposes. How to efficiently guide the search in the solution space of hard combinatorial problems whatever their underlying structure? The first purpose of this work is to provide efficient and generic search heuristics to guide the search toward promising areas and to solve hard practical problems. More specifically, the goal is to (1) develop new inference methods (which combine information from any kind of constraints imposed by the problem), (2) implement a framework to test these heuristics (so that we compute these heuristics over a variety of instances), and (3) assess the quality of these heuristics.;Contributions. Building upon the theoritical framework that has been proposed by Hsu et al. (2007), we derive new search heuristics that significantly improve the previous results obtained with this framework, and extend it to any CSP. One of the methods we propose (EMBP-Gsup) turns out to provide the most consistent results for the problems we consider when compared to what is (to the best of our knowledge) the current state of the art for solving these problems. This contribution has been published in (LeBras et al. (2009)).;Significance and theoritical background. Cambazard and Jussien (2005) em-phasize 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 maxSD (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.