The constraints listed here are sometimes called symbolic constraints. They are currently not reifiable. Unless documented otherwise, they maintain (at most) intervalconsistency in their arguments; see The Constraint System.
count(
+Val,
+List,
+RelOp,
?Count)
where Val is an integer, List is a list of integers or
domain variables, Count an integer or a domain
variable, and RelOp is a relational symbol as in
Arithmetic Constraints. True if N is the number of elements
of List that are equal to Val and N RelOp Count.
Thus, count/4
is a generalization of exactly/3
(not an
exported constraint), which was used in an example earlier.
count/4
maintains domainconsistency, but in practice, the
following constraint is a better alternative.
global_cardinality(
+Xs,
+Vals)
global_cardinality(
+Xs,
+Vals,
+Options)
where Xs = [X_1,\ldots,X_d] is a list of integers or domain variables, and Vals = [K_1V_1,\ldots,K_nV_n] is a list of pairs where each key K_i is a unique integer and V_i is a domain variable or an integer. True if every element of Xs is equal to some key and for each pair K_iV_i, exactly V_i elements of Xs are equal to K_i.
If either Xs or Vals is ground, and in many other
special cases, global_cardinality/[2,3]
maintains
domainconsistency, but generally, intervalconsistency cannot be
guaranteed. A domainconsistency algorithm [Regin 96] is used, roughly
linear in the total size of the domains.
Options is a list of zero or more of the following:
cost(
Cost,
Matrix)
With this option, a domainconsistency algorithm [Regin 99] is used, the complexity of which is roughly O(d(m + n \log n)) where m is the total size of the domains.
element(
?X,
+List,
?Y)
where X and Y are integers or domain variables and List is a list of integers or domain variables. True if the X:th element of List is Y. Operationally, the domains of X and Y are constrained so that for every element in the domain of X, there is a compatible element in the domain of Y, and vice versa.
This constraint uses an optimized algorithm for the special case where List is ground.
element/3
maintains domainconsistency in X and
intervalconsistency in List and Y.
relation(
?X,
+MapList,
?Y)
where X and Y are integers or domain variables and
MapList is a list of
integer

ConstantRange pairs, where the integer
keys occur uniquely (see Syntax of Indexicals). True if
MapList contains a pair
X

R and Y
is in the range denoted by R.
Operationally, the domains of X and Y are constrained so that for every element in the domain of X, there is a compatible element in the domain of Y, and vice versa.
If MapList is not ground, the constraint must be wrapped in
call/1
to postpone goal expansion until runtime.
An arbitrary binary constraint can be defined with relation/3
.
relation/3
is implemented in terms of the following, more
general constraint, with which arbitrary relations can be defined compactly:
case(
+Template,
+Tuples,
+Dag)
case(
+Template,
+Tuples,
+Dag,
+Options)
Template is an arbitrary nonground Prolog term. Its variables are merely placeholders; they should not occur outside the constraint nor inside Tuples.
Tuples is a list of terms of the same shape as Template. They should not share any variables with Template.
Dag is a list of nodes of the form
node(
ID,
X,
Successors)
, where X is a
placeholder variable. The set of all X should equal the
set of variables in Template. The first node in the
list is the root node. Let rootID denote its ID.
Nodes are either internal nodes or leaf nodes. In the
former case, Successors is a list of terms
(
Min..
Max)
ID2, where the ID2 refers to a
child node. In the latter case, Successors is a list of
terms
(
Min..
Max)
. In both cases, the
(
Min..
Max)
should form disjoint intervals.
ID is a unique, integer identifier of a node.
Each path from the root node to a leaf node corresponds to one set of tuples admitted by the relation expressed by the constraint. Each variable in Template should occur exactly once on each path, and there must not be any cycles.
Options is a list of zero or more of the following. It can be used to control the waking and pruning conditions of the constraint, as well as to identify the leaf nodes reached by the tuples:
leaves(
TLeaf,
Leaves)
on(
Spec)
prune(
Spec)
Spec is one of the following, where X is a placeholder variable occurring in Template or equal to TLeaf:
dom(
X)
min(
X)
max(
X)
minmax(
X)
val(
X)
none(
X)
The constraint holds if path(rootID,Tuple,Leaf) holds for each Tuple in Tuples and Leaf is the corresponding element of Leaves if given (otherwise, Leaf is a free variable).
path(ID,Tuple,Leaf) holds if Dag contains a term
node(
ID,
Var,
Successors)
, Var is the
unique k:th element of Template, i is the k:th
element of Tuple, and:
(
Min..
Max)
Child
,
(
Min..
Max)
,
For example, recall that element(
X,
L,
Y)
wakes
up when the domain of X or the lower or upper bound of Y has
changed, performs full pruning of X, but only prunes the bounds of
Y. The following two constraints:
element(X, [1,1,1,1,2,2,2,2], Y), element(X, [10,10,20,20,10,10,30,30], Z)
can be replaced by the following single constraint, which is equivalent declaratively as well as wrt. pruning and waking. The fourth argument illustrates the leaf feature:
elts(X, Y, Z, L) : case(f(A,B,C), [f(X,Y,Z)], [node(0, A,[(1..2)1,(3..4)2,(5..6)3,(7..8)4]), node(1, B,[(1..1)5]), node(2, B,[(1..1)6]), node(3, B,[(2..2)5]), node(4, B,[(2..2)7]), node(5, C,[(10..10)]), node(6, C,[(20..20)]), node(7, C,[(30..30)])], [on(dom(A)),on(minmax(B)),on(minmax(C)), prune(dom(A)),prune(minmax(B)),prune(minmax(C)), leaves(_,[L])]).
The DAG of the previous example has the following shape:
elts/4
 ? elts(X, Y, Z, L). L in 5..7, X in 1..8, Y in 1..2, Z in 10..30  ? elts(X, Y, Z, L), Z #>= 15. L in 6..7, X in(3..4)\/(7..8), Y in 1..2, Z in 20..30  ? elts(X, Y, Z, L), Y = 1. Y = 1, L in 5..6, X in 1..4, Z in 10..20  ? elts(X, Y, Z, L), L = 5. Z = 10, X in(1..2)\/(5..6), Y in 1..2
all_different(
+Variables)
all_different(
+Variables,
+Options)
all_distinct(
+Variables)
all_distinct(
+Variables,
+Options)
where Variables is a list of domain variables with bounded domains or integers. Each variable is constrained to take a value that is unique among the variables. Declaratively, this is equivalent to an inequality constraint for each pair of variables.
Options is a list of zero or more of the following:
on(
On)
dom
all_distinct/[1,2]
and assignment/[2,3]
),
to wake up when the domain of a variable is changed;
min
max
minmax
val
all_different/[1,2]
), to wake up when a variable becomes ground.
consistency(
Cons)
global
all_distinct/[1,2]
and assignment/[2,3]
.
A domainconsistency algorithm [Regin 94] is used, roughly linear in the
total size of the domains.
local
all_different/[1,2]
. An algorithm achieving
exactly the same pruning as a set of pairwise inequality constraints is
used, roughly linear in the number of variables.
bound
The following is a constraint over two lists of length n of variables. Each variable is constrained to take a value in [1,n] that is unique for its list. Furthermore, the lists are dual in a sense described below.
assignment(
+Xs,
+Ys)
assignment(
+Xs,
+Ys,
+Options)
where Xs = [X_1,\ldots,X_n] and Ys = [Y_1,\ldots,Y_n] are lists of domain variables or integers. True if all X_i, Y_i \in [1,n] and X_i=j \equiv Y_j=i.
Options is a list of zero or more of the following, where
Boolean must be true
or false
(false
is the
default):
on(
On)
all_different/2
.
consistency(
Cons)
all_different/2
.
circuit(
Boolean)
true
, circuit(
Xs,
Ys)
must hold for the
constraint to be true.
cost(
Cost,
Matrix)
With this option, a domainconsistency algorithm [Sellmann 02] is used, the complexity of which is roughly O(n(m + n \log n)) where m is the total size of the domains.
The following constraint can be thought of as constraining n nodes in a graph to form a Hamiltonian circuit. The nodes are numbered from 1 to n. The circuit starts in node 1, visits each node, and returns to the origin.
circuit(
+Succ)
circuit(
+Succ,
+Pred)
where Succ is a list of length n of domain variables or integers. The i:th element of Succ (Pred) is the successor (predecessor) of i in the graph. True if the values form a Hamiltonian circuit.
The following constraint can be thought of as constraining n tasks, each with a start time S_j and a duration D_j, so that no tasks ever overlap. The tasks can be seen as competing for some exclusive resource.
serialized(
+Starts,
+Durations)
serialized(
+Starts,
+Durations,
+Options)
where Starts = [S_1,\ldots,S_n] and Durations = [D_1,\ldots,D_n] are lists of domain variables with finite bounds or integers. Durations must be nonnegative. True if Starts and Durations denote a set of nonoverlapping tasks, i.e.:
for all 1 =< i<j =< n: Si+Di =< Sj OR Sj+Dj =< Si OR Di = 0 OR Dj = 0
The serialized/[2,3]
constraint is merely a special case of
cumulative/[4,5]
(see below).
Options is a list of zero or more of the following, where
Boolean must be true
or false
(false
is the
default, except for the bounds_only
option):
precedences(
Ps)
d(i,j,k)
, where i and j should be
task numbers, and k should be a positive integer or sup
,
denoting:
Si+k =< Sj OR Sj =< Si, if k is an integer Sj =< Si, if k is sup
i
j in
r
, where i and j should be
task numbers, and r should be a
ConstantRange (see Syntax of Indexicals), denoting:
SiSj #= Dij, Dij in r
resource(
R)
order_resource/2
(see Enumeration Predicates) in order to
find a consistent ordering of the tasks.
path_consistency(
Boolean)
true
, a redundant pathconsistency algorithm will be used
inside the constraint in an attempt to improve the pruning.
static_sets(
Boolean)
true
, a redundant algorithm will be used, which reasons about
the set of tasks that must precede (be preceded by) a given task, in an
attempt to tighten the lower (upper) bound of a given start
variable.
edge_finder(
Boolean)
true
, a redundant algorithm will be used, which attempts to
identify tasks that necessarily precede or are preceded by some set of tasks.
decomposition(
Boolean)
true
, an attempt is made to decompose the constraint each time
it is resumed.
bounds_only(
Boolean)
true
, the constraints will only prune the bounds of the
S_i variables, and not inside the domains.
Whether it's worthwhile to switch on any of the latter five options is highly problem dependent.
serialized/3
can model a set of tasks to be serialized with
sequencedependent setup times. For example, the following constraint
models three tasks, all with duration 5, where task 1 must precede task
2 and task 3 must either complete before task 2 or start at least 10
time units after task 2 started:
? domain([S1,S2,S3], 0, 20), serialized([S1,S2,S3], [5,5,5], [precedences([d(2,1,sup),d(2,3,10)])]). S1 in 0..15, S2 in 5..20, S3 in 0..20
The bounds of S1
and S2
changed because of the precedence
constraint. Setting S2
to 5 will propagate S1=0
and S3
in 15..20
.
The following constraint can be thought of as constraining n tasks to be placed in time and on m machines. Each machine has a resource limit, which is interpreted as a lower or upper bound on the total amount of resource used on that machine at any point in time that intersects with some task.
A task is represented by a term
task(O_i,D_i,E_i,H_i,M_i)
where O_i is the start
time, D_i the duration, E_i the end time, H_i the
resource consumption, and M_i a machine identifier.
A machine is represented by a term machine(M_j,L_j)
where M_j is the identifier and L_j is the resource limit
of the machine.
All fields are domain variables with bounded domains, or integers. L_j must be an integer. D_i must be nonnegative, but H_i may be either positive or negative. A negative resource consumption is interpreted as a resource demand.
cumulatives(
+Tasks,
+Machines)
cumulatives(
+Tasks,
+Machines,
+Options)
Options is a list of zero or more of the following, where
Boolean must be true
or false
(false
is the
default):
bound(
B)
lower
(the default), each resource limit is treated
as a lower bound.
If upper
, each resource limit is treated
as an upper bound.
prune(
P)
all
(the default), the constraint will try to prune as many
variables as possible. If next
, only variables that
occur in the first nonground task term (wrt. the order
given when the constraint was posted) can be pruned.
generalization(
Boolean)
true
, extra reasoning based on assumptions on machine
assignment will be done to infer more.
task_intervals(
Boolean)
true
, extra global reasoning will be performed in an attempt
to infer more.
The following constraint can be thought of as constraining n tasks, each with a start time S_j, a duration D_j, and a resource amount R_j, so that the total resource consumption does not exceed Limit at any time:
cumulative(
+Starts,
+Durations,
+Resources,
?Limit)
cumulative(
+Starts,
+Durations,
+Resources,
?Limit,
+Options)
where Starts = [S_1,\ldots,S_n], Durations = [D_1,\ldots,D_n], and Resource = [R_1,\ldots,R_n] are lists of domain variables with finite bounds or integers, and Limit is a domain variable with finite bounds or an integer. Durations, Resources and Limit must be nonnegative. Let:
a = min(S1,...,Sn), b = max(S1+D1,...,Sn+Dn) Rij = Rj, if Sj =< i < Sj+Dj Rij = 0 otherwise
The constraint holds if:
Ri1+...+Rin =< Limit, for all a =< i < b
If given, Options should be of the same form as in
serialized/3
, except the resource(
R)
option is not
useful in cumulative/5
.
The cumulative/4
constraint is due to Aggoun and Beldiceanu
[Aggoun & Beldiceanu 93].
The following constraint captures the relation between a list of values, a list of the values in ascending order, and their positions in the original list:
sorting(
+Xs,
+Ps,
+Ys)
where Xs = [X_1,\ldots,X_n], Ps = [P_1,\ldots,P_n], and Ys = [Y_1,\ldots,Y_n] are lists of domain variables or integers. The constraint holds if the following are true:
In practice, the underlying algorithm [Mehlhorn 00] is likely to achieve intervalconsistency, and is guaranteed to do so if Is is ground or completely free.
The following constraints model a set or lines or rectangles, respectively, so that no pair of objects overlap:
disjoint1(
+Lines)
disjoint1(
+Lines,
+Options)
where Lines is a list of terms F(S_j,D_j) or F(S_j,D_j,T_j), S_j and D_j are domain variables with finite bounds or integers denoting the origin and length of line j respectively, F is any functor, and the optional T_j is an atomic term denoting the type of the line. T_j defaults to 0 (zero).
Options is a list of zero or more of the following, where
Boolean must be true
or false
(false
is the
default):
decomposition(
Boolean)
true
, an attempt is made to decompose the constraint each time
it is resumed.
global(
Boolean)
true
, a redundant algorithm using global reasoning is used
to achieve more complete pruning.
wrap(
Min,
Max)
margin(T_1,T_2,D)
sup
. If sup
is
used, all lines of type T_2 must be placed before any line of type
T_1.
This option interacts with the wrap/2
option in the sense that
distances are counted with possible wraparound, and the distance
between any end point and origin is always finite.
The file library('clpfd/examples/bridge.pl')
contains an example where
disjoint1/2
is used for scheduling nonoverlapping tasks.
disjoint2(
+Rectangles)
disjoint2(
+Rectangles,
+Options)
where Rectangles is a list of terms F(S_j_1,D_j_1,S_j_2,D_j_2) or F(S_j_1,D_j_1,S_j_2,D_j_2,T_j), S_j_1 and D_j_1 are domain variables with finite bounds or integers denoting the origin and size of rectangle j in the X dimension, S_j_2 and D_j_2 are the values for the Y dimension, F is any functor, and the optional T_j is an atomic term denoting the type of the rectangle. T_j defaults to 0 (zero).
Options is a list of zero or more of the following, where
Boolean must be true
or false
(false
is the
default):
decomposition(
Boolean)
true
, an attempt is made to decompose the constraint each time
it is resumed.
global(
Boolean)
true
, a redundant algorithm using global reasoning is used
to achieve more complete pruning.
wrap(
Min1,
Max1,
Min2,
Max2)
inf
and sup
respectively. If they are integers, the space
in which the rectangles are placed should be thought of as a cylinder
wrapping around the X dimension where positions Min1 and
Max1 coincide. Furthermore, this option forces the domains of the
S_j_1 variables to be inside [Min1,Max11].
Min2 and Max2 should be either integers or the atoms
inf
and sup
respectively. If they are integers, the space
in which the rectangles are placed should be thought of as a cylinder
wrapping around the Y dimension where positions Min2 and
Max2 coincide. Furthermore, this option forces the domains of the
S_j_2 variables to be inside [Min2,Max21].
If all four are integers, the space is a toroid wrapping around both dimensions.
margin(T_1,T_2,D_1,D_2)
sup
. If
sup
is used, all rectangles of type T_2 must be placed
before any rectangle of type T_1 in the relevant dimension.
This option interacts with the wrap/4
option in the sense that
distances are counted with possible wraparound, and the distance
between any end point and origin is always finite.
The file library('clpfd/examples/squares.pl')
contains an example where
disjoint2/2
is used for tiling squares.
synchronization(
Boolean)
true
, a redundant algorithm is used
to achieve more complete pruning for the following case:
The following example shows an artificial placement problem involving 25
rectangles including four groups of rectangles whose left and right
borders must be aligned. If Synch
is true
, it can be
solved with firstfail labeling in 23 backtracks. If Synch
is false
, 60 million backtracks do not suffice to solve it.
ex([O1,Y1a,Y1b,Y1c, O2,Y2a,Y2b,Y2c,Y2d, O3,Y3a,Y3b,Y3c,Y3d, O4,Y4a,Y4b,Y4c], Synch) : domain([Y1a,Y1b,Y1c, Y2a,Y2b,Y2c,Y2d, Y3a,Y3b,Y3c,Y3d, Y4a,Y4b,Y4c], 1, 5), O1 in 1..28, O2 in 1..26, O3 in 1..22, O4 in 1..25, disjoint2([t(1,1,5,1), t(20,4,5,1), t(1,1,4,1), t(14,4,4,1), t(1,2,3,1), t(24,2,3,1), t(1,2,2,1), t(21,1,2,1), t(1,3,1,1), t(14,2,1,1), t(O1,3,Y1a,1), t(O1,3,Y1b,1), t(O1,3,Y1c,1), t(O2,5,Y2a,1), t(O2,5,Y2b,1), t(O2,5,Y2c,1), t(O2,5,Y2d,1), t(O3,9,Y3a,1), t(O3,9,Y3b,1), t(O3,9,Y3c,1), t(O3,9,Y3d,1), t(O4,6,Y4a,1), t(O4,6,Y4b,1), t(O4,6,Y4c,1)], [synchronization(Synch)]).
The following constraints express the fact that several vectors of domain variables are in ascending lexicographic order:
lex_chain(
+Vectors)
lex_chain(
+Vectors,
+Options)
where Vectors is a list of vectors (lists) of domain variables with finite bounds or integers. The constraint holds if Vectors are in ascending lexicographic order.
Options is a list of zero or more of the following:
op(
Op)
#=<
(the default), the constraints
holds if Vectors are in nondescending lexicographic order. If
Op is the atom #<
, the constraints holds if
Vectors are in strictly ascending lexicographic order.
among(
Least,
Most,
Values)
In the absence of an among/3
option, the underlying algorithm
[Carlsson & Beldiceanu 02] guarantees domainconsistency.