Link Search Menu Expand Document
Specifications PyCSP3 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 XCSP3: the function name appears first, followed by the operands between parenthesis (with comma as a separator). The XCSP3 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)
Opposite1neg(x) -x
Absolute Value 1abs(x) |x|
Addition $r\ge 2$ add$(x_1,\ldots,x_r)$ $x_1+ \ldots +x_r$
Subtraction 2sub(x,y) x-y
Multiplication $r \ge 2$ mul($x_1,\ldots,x_r$) $x_1 \times \ldots \times x_r$
Integer Division 2div(x,y) x / y
Remainder 2mod(x,y) x % y
Square 1sqr(x) x$^2$
Power 2pow(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 2dist(x,y) |x-y|
Relational (integer operands and Boolean result)
Less than 2lt(x,y) x < y
Less than or equal 2le(x,y) x $\le$ y
Greater than or equal 2ge(x,y) x $\ge$ y
Greater than 2gt(x,y) x > y
Different from 2ne(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 0set() $\emptyset$
Non-empty set $r \gt 0$ set($a_1,\ldots,a_r$) {$a_1,\ldots,a_r$}
Membership 2in(x,S) x $\in$ S
Logic (Boolean operands and Boolean result)
Logical not 1not(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 2imp(x,y) x $\Rightarrow$ y
Control
Alternative 3if(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.