The CLP Procedure

GCC Statement

  • GCC global_cardinality_constraint-1 <…global_cardinality_constraint-n>;

where global_cardinality_constraint is specified in the following form:

(variables) = ( $(v_1, l_1, u_1)$ <…$(v_ n, l_ n, u_ n)$> <DL= dl> <DU= du> )

$v_ i$ is a value in the domain of one of the variables, and $l_ i$ and $u_ i$ are the lower and upper bounds on the number of variables assigned to $v_ i$. The values of dl and du are the lower and upper bounds on the number of variables assigned to values in D outside of $\{ v_1,\ldots ,v_ n\} $.

The GCC statement specifies one or more global cardinality constraints. A global cardinality constraint (GCC) is a constraint that consists of a set of variables $\{ x_1,\dots ,x_ n\} $ and for each value v in $D=\bigcup _{i=1,\dots ,n} \mi{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$.

For example, the constraint that is specified with the statements 

var (x1-x6) = [1, 4];
gcc(x1-x6) = ((1, 1, 2) (2, 1, 3) (3, 1, 3) (4, 2, 3));

expresses that at least one but no more than two variables in ${x_1,\dots ,x_6}$ can have value 1, at least one and no more than three variables can have value 2 (or value 3), and at least two and no more than three variables can have value 4. For example, an assignment ${x_1=1, x_2=1, x_3=2, x_4=3, x_5=4}$, and ${x_6=4}$ satisfies the constraint.

If a global cardinality constraint has common lower or upper bounds for many of the values in D, the DL= and DU= options can be used to specify the common lower and upper bounds.

For example, the previous specification could also be written as 

gcc(x1-x6) = ((1, 1, 2) (4, 2, 3) DL=1 DU=3);

You can also specify missing values for the lower and upper bounds. The values of dl and du are substituted as appropriate. The previous example can also be expressed as 

gcc(x1-x6) = ((1, ., 2) (4, 2, .) DL=1 DU=3);

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

var (x1-x9) = [1, 9];
gcc(x1-x9) = (DL=0 DU=1);

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

var (x1-x9) = [1, 9];
alldiff(x1-x9);

If you do not specify the DL= and DU= options, the default lower and upper bound for any value in D that does not appear in the ${(v, l, u)}$ format is 0 and the number of variables in the constraint, respectively.

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 (x1-x9) = [0, 10];
 gcc(x1-x9) = ((1, 0, 0) (3, 0, 0) (5, 0, 0) (7, 0, 0) (9, 0, 0));

If the variable list is empty, the GCC constraint applies to all the variables declared in any VARIABLE statement.