The IC constraint solver has some optional components which provide so-called global constraints. These are high-level constraints that tend to provide more global reasoning than the constraints in the main IC library. These optional components are contained in the ic_global, ic_cumulative, ic_edge_finder and ic_edge_finder3 libraries. The ic_global library provides a collection of general global constraints, while the others provide constraints for resource-constrained scheduling.
To use these global constraints, load the relevant optional library or libraries using directives in one of these forms:
:- lib(ic_global). :- use_module(library(ic_global)). |
Specify this at the beginning of your program.
Note that some of these libraries provide alternate implementations of predicates which also appear in other libraries. For example, the alldifferent/1 constraint is provided by both the standard ic library and the ic_global library. This means that if you wish to use it, you must use the relevant module qualifier to specify which one you want: ic:alldifferent/1 or ic_global:alldifferent/1.
The alldifferent(List) predicate imposes the constraint on the elements of List that they all take different values. The standard alldifferent/1 predicate from the IC library provides a level of propagation equivalent to imposing pairwise #\=/2 constraints (though it does it more efficiently than that). This means that no propagation is performed until elements of the list start being made ground. This is despite the fact that there may be “obvious” inferences which could be made.
Consider as an example the case of 5 variables with domains 1..4. Clearly the 5 variables cannot all be given different values, since there are only 4 distinct values available. However, the standard alldifferent/1 constraint cannot determine this:
?- L = [X1, X2, X3, X4, X5], L :: 1 .. 4, ic:alldifferent(L).
X1 = X1{1 .. 4}
X2 = X2{1 .. 4}
X3 = X3{1 .. 4}
X4 = X4{1 .. 4}
X5 = X5{1 .. 4}
L = [X1{1 .. 4}, X2{1 .. 4}, X3{1 .. 4}, X4{1 .. 4}, X5{1 .. 4}]
There are 5 delayed goals.
Yes
Consider another example where three of the variables have domain 1..3. Clearly, if all the variables are to be different, then no other variable can take a value in the range 1..3, since each of those values must be assigned to one of the original three variables. Again, the standard alldifferent/1 constraint cannot determine this:
?- [X1, X2, X3] :: 1 .. 3, [X4, X5] :: 1 .. 5,
ic:alldifferent([X1, X2, X3, X4, X5]).
X1 = X1{1 .. 3}
X2 = X2{1 .. 3}
X3 = X3{1 .. 3}
X4 = X4{1 .. 5}
X5 = X5{1 .. 5}
There are 5 delayed goals.
Yes
On the other hand, ic_global’s alldifferent/1 constraint performs some stronger, more global reasoning, and for both of the above examples makes the appropriate inference:
?- L = [X1, X2, X3, X4, X5], L :: 1 .. 4, ic_global:alldifferent(L).
No
?- [X1, X2, X3] :: 1 .. 3, [X4, X5] :: 1 .. 5,
ic_global:alldifferent([X1, X2, X3, X4, X5]).
X1 = X1{1 .. 3}
X2 = X2{1 .. 3}
X3 = X3{1 .. 3}
X4 = X4{[4, 5]}
X5 = X5{[4, 5]}
There are 2 delayed goals.
Yes
Of course, there is a trade-off here: the stronger version of the constraint takes longer to perform its propagation. Which version is best depends on the nature of the problem being solved.
In a similar vein, the ic_cumulative, ic_edge_finder and ic_edge_finder3 libraries provide increasingly strong versions of constraints such as cumulative/4, but with increasing cost to do their propagation (linear, quadratic and cubic, respectively).