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