Differences between inference method and search method in constraint programming

Question

To solve a constraint problem, we can use inference method and/or search method. Constraint Propagation. Christian Bessiere, 2006 states in the very beginning: Constraint propagation is a form of inference, not search.

From my understanding, the inference method is to reduce domain. What does search method mean in CP? Many materials mentioned that constraint problems can be solved with inference method alone. How could it be possible? (My thought: During the inference steps, we still have to loop over constraints, then I think it also does searching for constraint processing. No search method used here?)

Basically, this question is about how inference method are different from search method. How can I tell that a solution used inference method only or search method only or both? Thank you in advance.

Answer 1

Let me clarify the difference between propagation and search :

Propagation : (also called Constraint Propagation, Filtering algorithms or inference methods) : Suppose we have the constraint $x+7 <= 9 $ such that the current domain of $x$ is $D(x) = {0,1,2,3,4} $, then one can infer that the values $3$ and $4$ should be removed. This process is called propagation. In general, each constraint C is associated to a propagator that, when invoked, look at the current domain of each variable in its scope and try to reduce them.

Search: Suppose now that we executed all the propagators of a given problem until no more filtering can occur. What a CP solver does, is to "branch" on a variable and assign it to a value, i.e. we decide to go to a new node in the search tree. The decision can indeed be a bad one, so we should be able to backtrack later and take another decision. This mechanism is called search, decision, branching.. and is usually performed using a heuristic.

State-of-the-art CP Solvers use the combination Search+Propagation (which can be seen as an improvement of DPLL (http://en.wikipedia.org/wiki/DPLL_algorithm) ). Note also that when the solver starts propagation, it never stop until a fix-point is reached, i.e. in order to be sure that no more domain reduction can occur.