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

Now let us replace the GAC algorithm by an algorithm that schedules a set of propagators:

procedure PROPAGATE
 Let Q be the set of constraints of G 
 while Q not empty do
  select and remove any constraint c from Q;
  get propagator p of for c;
  p.propagate();

But what happens if a propagator changed the domain of a variable x? We know that in this case all constraints that have x in its scope have to be put into Q again. You can decide to make Q, the constraint store, globally accessbile. Then each variable, that notices a change in its domain, can put the corresponding constraints into Q itself.

This strategy also helps us to maintain the consistency during the backtracking search. Depending on the branching strategy, after each branching step the domain of a variable is narrowed to one assignment or to a reduced value set. The variable, whose domain has been changed, updates the constraint store and triggers the propagation.

Implementing propagators

Now you can start to implement your own propagators. Let's start with some examples:

Propagator for x<y