The Constraint Programming Solver (Experimental)

GCC Predicate

  • GCC (variable-list,set-of-numeric-triplets)

The GCC predicate specifies a global cardinality constraint (GCC), which sets the minimum and maximum number of times each value can be assigned to a group of variables.

The syntax of the GCC constraint consists of two parts:

variable-list

See Common Syntax Components.

set-of-numeric-triplets

The triplets $<v,l_ v,u_ v>$ provide, for each value v, the minimum $l_ v$ and maximum $u_ v$ number of times that v can be assigned to the variables in the variable-list.

Consider the following statements: 

var X {1..6} >= 1 <= 4 integer;
con Mycon: gcc(X, /<1,1,2>, <2,1,3>, <3,1,3>, <4,2,3>/);

These statements specify a constraint that expresses the following requirements about the values of variables $\{ X[1],\dots ,X[6]\} $:

  • The value 1 must appear at least once but no more than twice.

  • The value 2 must appear at least once but no more than three times.

  • The value 3 must appear at least once but no more than three times.

  • The value 4 must appear at least twice but no more than three times.

The assignment ${X[1]=1, X[2]=1, X[3]=2, X[4]=3, X[5]=4}$, and ${X[6]=4}$ satisfies the constraint.

In general, a GCC constraint consists of a set of variables $\{ x_1,\dots ,x_ n\} $ and, for each value v in $D=\bigcup _{i=1,\dots ,n} \mr{Dom}(x_ i)$, a pair of numbers $l_ v$ and $u_ v$. A GCC is satisfied if and only if the number of times that a value v in D is assigned to the variables ${x_1,\dots ,x_ n}$ is at least $l_ v$ and at most $u_ v$.

Values in the domain of variable-list that do not appear in any triplet are unconstrained. They can be assigned to as many of the variables in variable-list as needed to produce a feasible solution.

The following statements specify that each of the values in the set $\{ 1,\dots ,9\} $ can be assigned to at most one of the variables ${X[1],\dots ,X[9]}$: 

var X {1..9} >= 1 <= 9 integer;
con Mycon: gcc(X, setof{i in 1..9} <i,0,1>);

Note that the preceding global cardinality constraint is equivalent to the all-different constraint that is expressed as follows: 

var X {1..9} >= 1 <= 9 integer;
con Mycon: alldiff(X);

The global cardinality constraint also provides a convenient way to define disjoint domains for a set of variables. For example, the following syntax limits assignment of the variables ${X[1],\dots ,X[9]}$ to even numbers between 0 and 10: 

var X {1..9} >= 0 <= 10 integer;
con Mycon: gcc(X, setof{i in 1..9 by 2} <i,0,0>);