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);

The REVISE procedure can be described as follows:

 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 c that comes to our mind. Just look at each tuple in the relation of c and decide, if it is valid or not. Notice that you need a check-procedure for each constraint that decides whether a tuple fulfills it or not. Although this always works, it can be very ineffective. For example, consider a constraint alldifferent(x_1,..,x_n) with n variables each having a domain of size d. Then the GAC algorithm runs in O(n*d^n) (for each variable we have to check d^n tuples). It is possible to design specialized algorithms that perform faster.

Of course, we 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 efficiently 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 a constraint than its propagator method. We say: The propagator implements a constraint. Unlike the REVISE procedure, we do not need a constraint checking method.

Scheduling of propagators