Specifications PyCSP³ Tools Instances Competitions About

Constraint intension

Intentional constraints form an important type of constraints. They are defined from Boolean expressions, usually called predicates. For example, the constraint x+y=z corresponds to an equation that is an expression evaluated to true or false according to the values assigned to the variables x, y and z. Predicates are represented under functional form in XCSP³: the function name appears first, followed by the operands between parenthesis (with comma as a separator). The XCSP³ representation of the constraint x+y=z is then eq(add(x,y),z). Operators on integers (including Booleans since we assume that false = 0 and true = 1) that can be used to build predicates are presented in the table below. When we refer to a Boolean operand or result, we mean either the integer value 0 or the integer value 1.

Below, $P$ denotes a predicate expression with $r$ formal parameters (not shown here, for simplicity), $X=\langle x_1,x_2,\ldots,x_r \rangle$ denotes a sequence of $r$ variables, the scope of the constraint, and $P(x_1,x_2,\ldots,x_r)$ denotes the value (0 or 1) returned by $P$ for any given instantiation of the variables in $X$.

intension($P$,$X$) with $P$ a predicate and $X=\langle x_1,x_2,\ldots,x_r \rangle$, iff $P(x_1,x_2,\ldots,x_r) = 1$

A constraint intension is defined by an element intension containing an element function that describes the functional representation of the predicate, referred to as boolExpr in the syntax box below, and whose precise syntax is given in the Syntax page.

Syntax

<intension>
  <function> boolExpr </function>
</intension>

Note that the opening and closing tags for function are optional, which gives:

Syntax

<intension> boolExpr </intension>  <!-- Simplified Form -->

The table of operators is:

Operation	Arity	Syntax	Semantics
Arithmetic (integer operands and integer result)
Opposite	1	neg(x)	-x
Absolute Value	1	abs(x)	\|x\|
Addition	$r\ge 2$	add$(x_1,\ldots,x_r)$	$x_1+ \ldots +x_r$
Subtraction	2	sub(x,y)	x-y
Multiplication	$r \ge 2$	mul($x_1,\ldots,x_r$)	$x_1 \times \ldots \times x_r$
Integer Division	2	div(x,y)	x / y
Remainder	2	mod(x,y)	x % y
Square	1	sqr(x)	x$^2$
Power	2	pow(x,y)	$x^y$
Minimum	$r \ge 2$	min($x_1,\ldots,x_r$)	min {$x_1,\ldots,x_r$}
Maximum	$r \ge 2$	max($x_1,\ldots,x_r$)	max {$x_1,\ldots,x_r$}
Distance	2	dist(x,y)	\|x-y\|
Relational (integer operands and Boolean result)
Less than	2	lt(x,y)	x < y
Less than or equal	2	le(x,y)	x $\le$ y
Greater than or equal	2	ge(x,y)	x $\ge$ y
Greater than	2	gt(x,y)	x > y
Different from	2	ne(x,y)	x $\ne$ y
Equal to	$r \ge 2$	eq($x_1,\ldots,x_r$)	$x_1= \ldots = x_r$
Set (a_i: integers, S: set of integers (no variable permitted), x: integer operand)
Empty set	0	set()	$\emptyset$
Non-empty set	$r \gt 0$	set($a_1,\ldots,a_r$)	{$a_1,\ldots,a_r$}
Membership	2	in(x,S)	x $\in$ S
Logic (Boolean operands and Boolean result)
Logical not	1	not(x)	$\lnot$ x
Logical and	$r \ge 2$	and($x_1,\ldots,x_r$)	$x_1 \land \ldots \land x_r$
Logical or	"r \\ge 2	or($x_1,\ldots,x_r$)	$x_1 \lor \ldots \lor x_r$
Logical xor	"r \\ge 2	xor($x_1,\ldots,x_r$)	$x_1 \oplus \ldots \oplus x_r$
Logical equivalence	$r \ge 2$	iff($x_1,\ldots,x_r$)	$x_1 \Leftrightarrow \ldots \Leftrightarrow x_r$
Logical implication	2	imp(x,y)	x $\Rightarrow$ y
Control
Alternative	3	if(b,x,y)	value of x, if b is true
			value of y, otherwise

For example, for constraints x+y=z and w ≥ z, we have:

Example

<intension> 
  <function> eq(add(x,y),z) </function>
</intension> 
<intension> 
  <function> ge(w,z) </function>
</intension>

or, equivalently, in simplified form:

Example

<intension> eq(add(x,y),z) </intension> 
<intension> ge(w,z) </intension>

Most of the time, intensional constraints correspond to primitive constraints which admit specialized filtering algorithms, such as the binary operators =, ≠, <, … When parsing, it is rather easy to identify those primitive constraints.

It is not possible to use compact lists of array variables and +/-infinity values in predicates.