Example of Defining a New Constraint

We will demonstrate creation of new constraints on the following example. To show that the constraints are not restricted to linear terms, we can take the constraint

X^2 + Y^2 =< C.

Assuming that X and Y are domain variables, we would like to define such a predicate that will be woken as soon as one or both variables' domains are updated in such a way that would require updating the other variable's domain, i.e. updates that would propagate via this constraint. For simplicity we assume that X and Y are nonnegative. We will define the predicate sq(X, Y, C) which will implement this constraint:

:- use_module(library(fd)).

% A*A + B*B <= C
sq(A, B, C) :-
    dvar_domain(A, DomA),
    dvar_domain(B, DomB),
    dom_range(DomA, MinA, MaxA),
    dom_range(DomB, MinB, MaxB),
    MiA2 is MinA*MinA,
    MaB2 is MaxB*MaxB,
    (MiA2 + MaB2 > C ->
        NewMaxB is fix(sqrt(C - MiA2)),
        dvar_remove_greater(B, NewMaxB)
    ;
        NewMaxB = MaxB
    ),
    MaA2 is MaxA*MaxA,
    MiB2 is MinB*MinB,
    (MaA2 + MiB2 > C ->
        NewMaxA is fix(sqrt(C - MiB2)),
        dvar_remove_greater(A, NewMaxA)
    ;
        NewMaxA = MaxA
    ),
    (NewMaxA*NewMaxA + NewMaxB*NewMaxB =< C ->
        true
    ;
        suspend(sq(A, B, C), 3, (A, B)->min)
    ),
    wake. % Trigger the propagation

The steps to be executed when this constraint becomes active, i.e. when the predicate sq/3 is called or woken are the following:

1.

We access the domains of the two variables using the predicate dvar_domain/2 and and obtain their bounds using dom_range/3. Note that it may happen that one of the two variables is already instantiated, but these predicates still work as if the variable had a singleton domain.

2.

We check if the maximum of one or the other variable is still consistent with this constraint, i.e. if there is a value in the other variable's domain that satisfies the constraint together with this maximum.

3.

If the maximum value is no longer consistent, we compute the new maximum of the domain, and then update the domain so that all values greater than this value are removed using the predicate dvar_remove_greater/2. This predicate also wakes all concerned suspension lists and instantiates the variable if its new domain is a singleton.

4.

After checking the updates for both variables we test if the constraint is now satisfied for all values in the new domains. If this is not the case, we have to suspend the predicate so that it is woken as soon as the minimum of either domain is changed. This is done using the predicate suspend/3.

5.

The last action is to trigger the execution of all goals that are waiting for the updates we have made. It is necessary to wake these goals after inserting the new suspension, otherwise updates made in the woken goals would not be propagated back to this constraint.

Here is what we get:

[eclipse 20]: [X,Y]::1..10, sq(X, Y, 50).

X = X{[1..7]}
Y = Y{[1..7]}

Delayed goals:
	sq(X{[1..7]}, Y{[1..7]}, 50)
yes.
[eclipse 21]: [X,Y]::1..10, sq(X, Y, 50), X #> 5.

Y = Y{[1..3]}
X = X{[6, 7]}

Delayed goals:
	sq(X{[6, 7]}, Y{[1..3]}, 50)
yes.
[eclipse 22]: [X,Y]::1..10, sq(X, Y, 50), X #> 5, Y #> 1.

X = 6
Y = Y{[2, 3]}
yes.
[eclipse 23]: [X,Y]::1..10, sq(X, Y, 50), X #> 5, Y #> 2.

X = 6
Y = 3
yes.