Previous Up Next

14.3  Constraint Behaviours

As opposed to the theoretical CSP framework sketched in the previous section, in ECLiPSe we usually deal with more heterogeneous situation. We want to allow the integration of very different constraints, and we want to achieve a separation of constraint propagation and search. Therefore, we are not interested in an overall problem solving algorithm which controls search and constraint propagation globally for the whole problem and all constraints. We prefer to view the constraint solving process as in figure 14.1: the search process is controlled by an algorithmic program, while constraint propagation is performed by data-driven agents which do local (again algorithmic) computations on one or several constraints.

Figure 14.1: Control during Constraint Solving

Individual constraints can then be implemented with different behaviours, and freely mixed within a single computation. Constraint behaviours can essentially be characterised by

Let us now look at examples of different constraint behaviours.

14.3.1  Consistency Check

The =</2 predicate, whose standard Prolog version raises an error when invoked with uninstantiated variable, is also implemented by the suspend library. Both implementations have the same declarative meaning, but the suspend version can be considered to be a proper constraint. It implements a passive test, i.e. it simply delays until both arguments are numbers, and then succeeds or fails:

?- suspend : (X =< 4).
X = X
There is 1 delayed goal.
Yes (0.00s cpu)

?- suspend : (X =< 4), X = 2.
X = 2
Yes (0.00s cpu)

?- suspend : (X =< 4), X = 5.
No (0.00s cpu)

14.3.2  Forward Checking

Often a constraint can already do useful work before all its arguments are instantiated. In particular, this is the case when we are working with domain variables. Consider ic’s disequality constraint #\= : Even when only one side is instantiated, it can already remove this value from the domain of the other (still uninstantiated) side:

?- X :: 1 .. 5,
   X #\= 3.
X = X{[1, 2, 4, 5]}
Yes (0.00s cpu)

If both sides are uninstantiated, the constraint cannot do anything useful. It therefore waits (delays) until one side becomes instantiated, but then wakes up and acts as before. This behaviour is sometimes called forward checking [27]:

?- [X,Y] :: 1 .. 5,
   X #\= Y.        % delays
X = X{1 .. 5}
Y = Y{1 .. 5}
There is 1 delayed goal.
Yes (0.00s cpu)

?- X :: 1 .. 5,
   X #\= Y,         % delays
   Y = 3.           % wakes
X = X{[1, 2, 4, 5]}
Y = 3
Yes (0.01s cpu)

14.3.3  Domain (Arc) Consistency

For many constraints, even more eager behaviour is possible. For example, ic’s inequality constraints performs domain updates as soon as possible, even when one or both arguments are still variables:

?- [X, Y] :: 1 .. 5, X #< Y.
X = X{1 .. 4}
Y = Y{2 .. 5}
There is 1 delayed goal.
Yes (0.00s cpu)

?- [X, Y] :: 1 .. 5, X #< Y, X #> 2.
Y = Y{[4, 5]}
X = X{[3, 4]}
There is 1 delayed goal.
Yes (0.00s cpu)

Inconsistent values are removed form the domains as soon as possible. This behaviour corresponds to arc consistency as discussed in section 14.2.

14.3.4  Bounds Consistency

Note however that not all ic constraints maintain full domain arc consistency. For performance reasons, the #= constraint only maintains bounds consistency, which is weaker, as illustrated by the following example:

?- [X, Y] :: 1 .. 5, X #= Y + 1, X #\= 3.
Y = Y{1 .. 4}
X = X{[2, 4, 5]}
There is 1 delayed goal.
Yes (0.00s cpu)

Here, the value 2 for Y was not removed even though it is not arc consistent (there is no value for X which is compatible with it).

It is important to understand that this kind of propagation incompleteness does not affect correctness: the constraint will simply detect the inconsistency later, when its arguments have become more instantiated. In terms of the search tree, this means that a branch will not be pruned as early as possible, and extra time might be spent searching.

Consistency Checking
wait until all variables instantiated, then check
Forward Checking
wait until one variable left, then compute consequences
Domain (Arc) Consistency
wait until a domain changes, then compute consequences for other domains
Bounds Consistency
wait until a domain bound changes, then compute consequences for other bounds
Figure 14.2: Typical Constraint Behaviours

Previous Up Next