5.135. global_cardinality
| DESCRIPTION | LINKS | GRAPH | AUTOMATON |
- Origin
- Constraint
global_cardinality(VARIABLES,VALUES)
- Synonym(s)
count, distribute, distribution, gcc, card_var_gcc, egcc, extended_global_cardinality.
- Argument(s)
-
VARIABLES collection(var−dvar) VALUES collection(val−int,noccurrence−dvar) - Restriction(s)
-
required(VARIABLES,var) required(VALUES,[val,noccurrence]) distinct(VALUES,val) VALUES.noccurrence≥0 VALUES.noccurrence≤|VARIABLES| - Purpose
Each value VALUES[i].val (1≤i≤|VALUES|) should be taken by exactly VALUES[i].noccurrence variables of the VARIABLES collection.
- Example
-
(
)〈3,3,8,6〉, 〈val−3 noccurrence−2,val−5 noccurrence−0,val−6 noccurrence−1〉 The global_cardinality constraint holds since values 3, 5 and 6 respectively occur 2, 0 and 1 times within the collection 〈3,3,8,6〉 and since no constraint was specified for value 8.
- Usage
We show how to use the global_cardinality constraint in order to model the magic series problem [VanHentenryck89] with one single global_cardinality constraint. A non-empty finite series S=(s0,s1,...,sn) is magic if and only if there are si occurrences of i in S for each integer i ranging from 0 to n. This leads to the following constraint:
global_cardinality(
)〈
〉,var−s0,var−s1,...,var−sn 〈
〉val−0 noccurrence−s0, val−1 noccurrence−s1, ⋮ val−n noccurrence−sn - Remark
This is a generalised form of the original global_cardinality constraint: in the original global_cardinality constraint [Regin96], one specifies for each value its minimum and maximum number of occurrences (i.e., see global_cardinality_low_up). Here we give for each value v a domain variable that indicates how many time value v is effectively used. By setting the minimum and maximum values of this variable to the appropriate constants we can express the same thing as in the original global_cardinality constraint. However, as shown in the magic series problem, we can also use this variable in other constraints. By reduction from 3-SAT, Claude -Guy Quimper shows in [Quimper03] that it is NP -hard to achieve arc-consistency for the count variables.
A last difference with the original global_cardinality constraint comes from the fact that there is no constraint on the values that are not mentioned in the VALUES collection. In the original global_cardinality these values could not be assigned to the variables of the VARIABLES collection.
Within [BourdaisGalinierPesant03] the global_cardinality constraint is called distribution. Within [ReginGomes04] the global_cardinality constraint is called card_var_gcc. Within [BessiereHebrardHnichWalsh04a] the global_cardinality constraint is called egcc or rgcc. This later case corresponds to the fact that some variables are duplicated within the VARIABLES collection.
W.-J. van Hoeve et al. present two soft versions of the global_cardinality constraint in [HoevePesantRousseau04].
- Algorithm
A flow algorithm that handles the original global_cardinality constraint is described in [Regin96]. The two approaches that were used to design bound-consistency algorithms for alldifferent were generalised for the global_cardinality constraint. The algorithm in [QuimperBeekOrtizGolynskiSadjad03] identifies Hall intervals and the one in [KatrielThiel03] exploits convexity to achieve a fast implementation of the flow -based arc-consistency algorithm. The later algorithm can also compute bound-consistency for the count variables [KatrielThielConstraints05], [Katriel05]. An improved algorithm for achieving arc-consistency is described in [QuimperLopezOrtizBeekGolynski04].
- Systems
globalCardinality in Choco, count in Gecode, gcc in Jacop, global_cardinality in SICStus.
- See also
among, count, open_global_cardinality, nvalue, max_nvalue, min_nvalue, global_cardinality_with_costs, symmetric_gcc, symmetric_cardinality, colored_matrix, same_and_global_cardinality, global_cardinality_no_loop, ordered_global_cardinality.
- Key words
-
characteristic of a constraint: core, automaton, automaton with array of counters.
constraint type: value constraint.
filtering: Hall interval, bound-consistency, flow, duplicated variables, DFS-bottleneck.
For all items of VALUES:
- Arc input(s)
VARIABLES
- Arc generator
-
SELF↦collection(variables) - Arc arity
-
1 - Arc constraint(s)
-
variables.var=VALUES.val - Graph property(ies)
-
NVERTEX=VALUES.noccurrence
- Graph model
Since we want to express one unary constraint for each value we use the “For all items of VALUES” iterator. Part (A) of Figure 5.135.1 shows the initial graphs associated with each value 3, 5 and 6 of the VALUES collection of the Example slot. Part (B) of Figure 5.135.1 shows the two corresponding final graphs respectively associated with values 3 and 6 that are both assigned to the variables of the VARIABLES collection (since value 5 is not assigned to any variable of the VARIABLES collection the final graph associated with value 5 is empty). Since we use the NVERTEX graph property, the vertices of the final graphs are stressed in bold.
Figure 5.135.1. Initial and final graph of the global_cardinality constraint
(a) (b)
- Automaton
Figure 5.135.2 depicts the automaton associated with the global_cardinality constraint. To each item of the collection VARIABLES corresponds a signature variable Si that is equal to 0. To each item of the collection VALUES corresponds a signature variable Si+|VARIABLES| that is equal to 1.
Figure 5.135.2. Automaton of the global_cardinality constraint
