Link Search Menu Expand Document
Specifications PyCSP3 Tools Instances Competitions About
Specifications
XCSP web site is provided by CRIL
This site uses Just the Docs, a documentation theme for Jekyll.

Groups (and constraint templates)

A constraint template is a kind of constraint abstraction, that is to say, an element representing a constraint in XCSP3 where some formal parameters are present (typically, for representing missing values and/or variables). Such parameters are denoted by the symbol % followed by a parameter index. A constraint template has p ≥ 1 parameters(s), with indices going from 0 to p-1, and of course, a parameter can appear several times.

For example, here is a constraint template, with three parameters, for the element intension:

Example 

<intension> eq(add(%0,%1),%2) </intension>

and another one, with two parameters, for the element extension:

Example 

<extension>
  <list> %0 %1 </list>
  <supports> (1,2)(2,1)(2,3)(3,1)(3,2)(3,3) </supports>
</extension>

A constraint template must be used in a context that permits to furnish the actual parameters, or arguments. A first possibility is within constraints slide and seqbin, where the arguments are automatically given by the variables of a sequence (sliding effect). A second possibility is to build an element group whose role is to encapsulate a constraint template followed by a sequence of elements args. Each element args must contain as many arguments as the number of parameters in the constraint template (using whitespace as separator). Of course, the first argument in args corresponds to %0, the second one to %1, and so on.

Do note that a constraint template can only be found in elements slide, seqbin and group, and that no two such elements can be related by an ancestor-descendant relationship.

Considering constraints over integer variabless, an argument can be any integer functional expression, referred to as intExpr in the syntax box below (its precise syntax is given in the Syntax page). When parsing, a solver has to replace the formal parameters of the predicate template by the corresponding arguments to build the constraint.

As a formal parameter, in the context of a group, it is also possible to use %... that stands for a variable number of arguments. If %i is the formal parameter with the highest index i present in the template, then %... will be replaced by the sequence (whitespace as separator) of arguments that come after the one associated with %i. If %... is the only formal parameter present in the template, then %... will be replaced by the full sequence of arguments.

It is currently forbidden to use %... inside elements slide and seqbin. Also, note that %... can never occur in a functional expression (for example, add(x,%...) is clearly invalid).

The syntax for the element group, admitting an optional attribute id, is:

Syntax 

<group  [ id="identifier" ]>
  <constraint.../>  <!-- constraint template -->
  (<args> (intExpr wspace)+ </args>)2+
</group>

To summarize, an element group defines a group of constraints sharing the same constraint template. This is equivalent to posting as many constraints as the number of elements args inside group. When the attribute id is specified for a group, we can consider that the id of each constraint is given by the id of the group followed by [i] where i denotes the position (starting at 0) of the constraint inside the group. At this point, it should be clear that (syntactic) groups are useful. First, they permit to partially preserve the structure of the problem. Second, there is no need to parse several times the constraint template. Third, the representation is made more compact.

Let us illustrate this important concept of syntactic groups of constraints. The following group of constraints is equivalent to post:

  • g[0]: x0+x1=x2
  • g[1]: x3+x4=x5
  • g[2]: x6+x7=x8

Example 

<group id="g">
  <intension> eq(add(%0,%1),%2) </intension>
  <args> x0 x1 x2 </args> 
  <args> x3 x4 x5 </args> 
  <args> x6 x7 x8 </args>
</group>

With T={(1, 2),(2,1),(2,3),(3,1),(3,2),(3,3)}, the following group of constraints is equivalent to post:

  • h[0]: $\langle$ w,x $\rangle \in$ T
  • h[1]: $\langle$ w,z $\rangle \in$ T
  • h[2]: $\langle$ x,y $\rangle \in$ T

Example 

<group id="h">  
  <extension>
    <list> %0 %1 </list>
    <supports> (1,2)(2,1)(2,3)(3,1)(3,2)(3,3) </supports>
  </extension>
  <args> w x </args>
  <args> w z </args>
  <args> x y </args>
</group>

Now, we give the XCSP3 formulation for the 3-order instance of the Latin Square problem (fill an $n \times n$ array with n different symbols, such that each symbol occurs exactly once in each row and exactly once in each column).

Example 

<instance format="XCSP<sup>3</sup>" type="CSP">
  <variables>
    <array id="x" size="[3][3]"> 1..3 </array>
  </variables>
  <constraints>
    <group>  
      <allDifferent> %0 %1 %2 </allDifferent>
      <args> x[0][0] x[0][1] x[0][2] </args>
      <args> x[1][0] x[1][1] x[1][2] </args>
      <args> x[2][0] x[2][1] x[2][2] </args>
      <args> x[0][0] x[1][0] x[2][0] </args>
      <args> x[0][1] x[1][1] x[2][1] </args>
      <args> x[0][2] x[1][2] x[2][2] </args>
    </group>
  </constraints>
</instance>

Note that we can use shorthands for lists of variables taken from arrays, and also the formal parameter %…, as illustrated by:

Example 

<instance format="XCSP<sup>3</sup>" type="CSP">
  <variables>
    <array id="x" size="[3][3]"> 1..3 </array>
  </variables>
  <constraints>
    <group>  
      <allDifferent> %... </allDifferent>
      <args> x[0][] </args>  
      <args> x[1][] </args>  
      <args> x[2][] </args>
      <args> x[][0] </args>
      <args> x[][1] </args>
      <args> x[][2] </args>
    </group>
  </constraints>
</instance>

Of course, in this very special context, a group is not very useful as it is possible to use the constraint {gb(“allDifferent-matrix”)}, leading to:

Example 

<instance format="XCSP<sup>3</sup>" type="CSP">
  <variables>
    <array id="x" size="[3][3]"> 1..3 </array>
  </variables>
  <constraints>
    <allDifferent>  
      <matrix> x[][] </matrix>
    </allDifferent>
  </constraints>
</instance>

As a last illustration, we give the XCSP3 formulation for the 3-order instance of the Magic Square problem. Note that we cannot replace the element group by a more compact representation.

Example 

<instance format="XCSP<sup>3</sup>" type="CSP">
  <variables>
    <array id="x" size="[3][3]"> 1..9 </array>
  </variables>
  <constraints>
    <allDifferent> x[][] </allDifferent>
    <group>
      <sum>
        <list> %... </list>
        <condition> (eq,15) </condition>
      </sum>
      <args> x[0][] </args>
      <args> x[1][] </args>
      <args> x[2][] </args>
      <args> x[][0] </args>
      <args> x[][1] </args>
      <args> x[][2] </args>
      <args> x[0][0] x[1][1] x[2][2] </args>
      <args> x[2][0] x[1][1] x[0][2] </args>
    </group> 
  </constraints>
</instance>

Note that an element group (i) cannot be reified, as it is considered as a set of constraints, and not a single one, (ii) cannot be relaxed/softened, for the same reason, (iii) can only be a child of constraints or a child of an element block; hence, it cannot be a descendant of (i.e., involved in) an element group, slide or seqbin.