Simple User-defined Constraints

8.6 Simple User-defined Constraints

User-defined, or ‘conceptual’ constraints can easily be defined as conjunctions of primitive constraints. For example, let us consider a set of products and the specification that allows them to be colocated in a warehouse. This should be done in such a way as to propagate possible changes in the domains as soon as this becomes possible.

Let us assume we have a symmetric relation that defines which product can be colocated with another and that products are distinguished by numeric product identifiers:

colocate(100, 101).
colocate(100, 102).
colocate(101, 100).
colocate(102, 100).
colocate(103, 104).
colocate(104, 103).

Suppose we define a constraint colocate_product_pair(X, Y) such that any change of the possible values of X or Y is propagated to the other variable. There are many ways in which this pairing can be defined in ECLⁱPS^e. They are different solutions with different properties, but they yield the same results.

8.6.1 Using Reified Constraints

We can encode directly the relations between elements in the domains of the two variables:

colocate_product_pair(A, B) :-
    cpp(A, B),
    cpp(B, A).

cpp(A, B) :-
    [A,B] :: [100, 101, 102, 103, 104],
    A #= 100 => B :: [101, 102],
    A #= 101 => B #= 100,
    A #= 102 => B #= 100,
    A #= 103 => B #= 104,
    A #= 104 => B #= 103.

This method is quite simple and does not need any special analysis; on the other hand it potentially creates a huge number of auxiliary constraints and variables.

8.6.2 Using Propia

By far the simplest mechanism, that avoids this potential creation of large numbers of auxiliary constraints and variables, is to load the Generalised Propagation library (propia) and use arc-consistency (ac) propagation, viz:

?- colocate(X,Y) infers ac

⊙: Additional information on propia can be found in section 15.3, section 15 and the ECLⁱPS^e Constraint Library Manual.

8.6.3 Using the element Constraint

In this case we use the element/3 predicate, that states in a list of integers that the element at an index is equal to a value. Every time the index or the value is updated, the constraint is activated and the domain of the other variable is updated accordingly.

relates(X, Xs, Y, Ys) :-
    element(I, Xs, X),
    element(I, Ys, Y).

We define a generic predicate, relates/4, that associates the corresponding elements at a specific index of two lists, with one another. The variable I is an index into the lists, Xs and Ys, to yield the elements at this index, in variables X and Y.

colocate_product_pair(A, B) :-
    relates(A, [100, 100, 101, 102, 103, 104], 
            B, [101, 102, 100, 100, 104, 103]).

The colocate_product_pair predicate simply calls relates/4 passing a list containing the product identifiers in the first argument of colocate/2 as Xs and a list containing product identifiers from the second argument of colocate/2 as Ys.

Behind the scenes, this is exactly the implementation used for arc-consistency propagation by the Generalised Propagation library.

Because of the specific and efficient algorithm implementing the element/3 constraint, it is usually faster than the first approach, using reified constraints.