Specifications PyCSP³ Tools Instances Competitions About

Constraint cardinality

The constraint cardinality, also called globalCardinality or gcc in the literature, see [R96] and [H12], ensures that the number of occurrences of each value in values, taken by variables of list, is related to a corresponding element (value, variable or interval) in occurs. The element values has an optional attribute closed (true, by default): when closed=true, this means that all variables of list must be assigned a value from values.

For simplicity, for the semantics, we assume that V only contains values and O only contains variables. Note that $V^{cl}$ means that closed=true.

cardinality($X$, $V$, $O$) with $X=\langle x_1,x_2,\ldots \rangle$ $V=\langle v_1,v_2,\ldots \rangle$ and $O=\langle o_1, o_2,\ldots \rangle$, iff $\forall j : 1 \leq j \leq |V|, |\{i : 1 \leq i \leq |X| \land x_i =v_j\}| = o_i$
cardinality($X$, $V^{cl}$, $O$), iff cardinality($X$, $V$, $O$) and$\forall i : 1 \leq i \leq |X|, x_i \in V$

Syntax

<cardinality>
  <list> (intVar wspace)2+ </list>
  <values  [ closed="boolean" ]> (intVal wspace)+ | (intVar wspace)+ </values>
  <occurs> (intVal wspace)+ | (intVar wspace)+ | (intIntvl wspace)+ </occurs>
</cardinality>

In the following example, the first constraint states that value 2 must be assigned to 0 or 1 variable (among x1, x2, x3, x4), value 5 must be assigned by at least 1 and at most 3 variables, and value 10 by at least 2 and at most 3 variables. For the second constraint, the number of variables from y1, y2, y3, y4, y5 that take value 0 must be equal to z0, and so on. Note that it is possible for a variable to be assigned a value not present in {0,1,2,3} since closed=false.

Example

<cardinality>
  <list> x1 x2 x3 x4 </list>
  <values> 2 5 10 </values>
  <occurs> 0..1 1..3 2..3 </occurs>
</cardinality>
<cardinality>
  <list> y1 y2 y3 y4 y5 </list>
  <values closed="false"> 0 1 2 3 </values>
  <occurs> z0 z1 z2 z3 </occurs>
</cardinality>

The form of the constraint obtained by only considering variables in all contained elements is called distribute in MiniZinc. In that case, for the semantics, me must additionally guarantee: $\forall (i,j) : 1 \leq i \lt j \leq |V|, v_i \neq v_j$.

Example

<cardinality>
  <list> w1 w2 w3 w4 </list>
  <values> v1 v2 </values>
  <occurs> n1 n2 </occurs>
</cardinality>

The constraint increasing_global_ardinality defined in the Global Constraints Catalog can be built by adding restriction increasing to list, but this is not allowed in XCSP³-core.