Constraint Processing

Introduction

In out lecture you already learned about a generic backtracking algorithm that is able to solve any Constraint Satisfaction Problem (CSP) with variables, domains and constraints. In order to reduce the search space, we used forward checking and arc consistency methods. These algorithms remove inconsistent values from the domains of the variables, that are not yet part of the partial solution. They work for binary constraints as well as for non-binary constraints. For the latter, just recapitulate one possible generic arc consistency algorithm:

procedure GAC(G)
 Let Q be the set of (undirected) constraints of G 
 while Q not empty do
  select and remove any constraint c from Q;
  for each variable x participating in c
    REVISE(x,c)
    if REVISE(x,c) changed the domain of x then
      add to Q the set of all constraints that include x (except c);

 procedure REVISE (x,c)
     for each value a in domain of x do
       if there is no tuple in the relation of c that includes (x,a) and is valid
           then delete a from the domain of x

We could reuse this algorithm to check any constraint that comes to our mind. Just look at each tuple in the relation of c and decide, if it is valid or not. Although this always works, it can be very ineffective. Of course, we really want to remove exactly those inconsistent values the REVISE-procedure is looking for. However, it is often better not to take the procedure literally! Instead we want to write constraint-specific filtering methods, that exploit the semantics of a constraint.

What I mean is, each constraint should be responsible for maintaining a consistent state of the domains of the variables in its scope. Each constraint should be associated with a specific procedure, that removes values from the domains that are not part of a valid tuple in the relation. We call this procedure propagator. Our constraint solver doesn't need to know more about our constraint than its propagator method. We say: The propagator implements a constraint. As with other consistency methods (FC, AC, GAC) we do not need a constraint checking method or something like that, because the solver can only assign values, that are valid with regard to the state of the partial solution - the propagators of the constraints ensure that there are only valid values in their domains.