Specifications PyCSP³ Tools Instances Competitions About

Constraint extension

Extensional constraints, also called table constraints (especially, when constraint arity is large), are defined by enumerating the list of tuples that are allowed (supports) or forbidden (conflicts).

A constraint extension contains then two elements. The first element is an element list that indicates the scope of the constraint (necessarily a list of variable ids). The second element is either an element supports or an element conflicts, depending on the semantics of the (ordinary) tuples that are listed in lexicographic order within the element.

Positive Table Constraints

Positive table constraints are defined from supports.

extension($X$,$S$) with $X=\langle x_1,\ldots,x_r \rangle$ and $S$ a set of supports, iff $\langle x_1,\ldots,x_r \rangle \in S$

The syntax for unary extensional positive constraints is:

Syntax

<extension>
  <list> intVar </list>
  <supports>  ((intVal | intIntvl) wspace)\* </supports>
</extension>

The syntax for non-unary extensional positive constraints is:

Syntax

<extension>
  <list> (intVar wspace)2+ </list>
  <supports> ("(" intVal ("," intVal)+ ")")\* </supports>
</extension>

An example is given below with a unary constraint involving x, with {1,2,4,8,9,10} as supports, and a ternary constraint involving y1, y2 and y3, with {(0, 1, 0),(1,0,0),(1,1,0),(1,1,1)} as supports.

Example

<extension id="c1">
  <list> x </list>
  <supports> 1 2 4 8..10 </supports>
</extension>
<extension id="c2">
  <list> y1 y2 y3 </list>
  <supports> (0,1,0)(1,0,0)(1,1,0)(1,1,1) </supports>
</extension>

Negative Table Constraints

Negative table constraints are defined from conflicts.

extension($X$,$C$) with $X=\langle x_1,\ldots,x_r \rangle$ and $C$ a set of conflicts, holds iff $\langle x_1,\ldots,x_r \rangle \notin C$

The syntax for unary extensional negative constraints is:

Syntax

<extension>
  <list> intVar </list>
  <conflicts> ((intVal | intIntvl) wspace)\* </conflicts>
</extension>

The syntax for non-unary extensional negative constraints is:

Syntax

<extension>
  <list> (intVar wspace)2+ </list>
  <conflicts> ("(" intVal ("," intVal)+ ")")\* </conflicts>
</extension>

An example is given below with a unary constraint involving x, with {2,6} as conflicts, and a quaternary constraint involving y1, y2, y3 and y4, with {(1, 2, 3, 4),(3,1,3,4)} as conflicts.

Example

 <extension>
  <list> x </list>
  <conflicts> 2 6 </conflicts>
</extension>
<extension>   
  <list> y1 y2 y3 y4 </list>
  <conflicts> (1,2,3,4)(3,1,3,4) </conflicts> 
</extension>

Non-ordinary Tables

We now introduce extended forms of non-unary table constraints: they involve non-ordinary tuples, i.e., short or compressed tuples. On the one hand, it may be particularly useful to integrate short tuples (based on so-called short supports) in tables. This means that we can insert the special symbol “*” in tuples to represent any possible value, for the associated variable(s).
For example, the following constraint has two short tuples, (1,*,1,2) and (2,1,*,*). Assuming that the domain of all variables is {1,2}, the first short tuple is equivalent to the two (long) tuples (1,1,1,2) and (1,2,1,2) whereas the second short tuple is equivalent to the four tuples (2,1,1,1), (2,1,1,2), (2,1,2,1) and (2,1,2,2).

Example

<extension>
  <list> z1 z2 z3 z4 </list>
  <supports> (1,*,1,2)(2,1,*,*) </supports>
</extension>

On the other hand, to reduce space complexity, one may also seek to integrate compressed tuples in tables. This means that tuples can contain not only usual integer values, but also sets of integer values. The set of classical tuples represented by a compressed tuple τ is then the Cartesian product built from the components of τ. For example, in the following constraint, (0,{1,2},0,{0,2}) is a compressed tuple representing the set of ordinary tuples in {0}×{1,2}×{0}×{0,2}, which contains (0,1,0,0), (0,1,0,2), (0,2,0,0) and (0,2,0,2).

Example

<extension>
  <list> w1 w2 w3 w4 </list>
  <supports> (0,{1,2},0,{0,2})(1,0,1,2)(2,{0,2},0,2) </supports>
</extension>

In XCSP³-core, short tuples are considered, contrary to compressed tuples.