5.30. atleast_nvalue
| DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Synonym
.
- Arguments
- Restrictions
- Purpose
The number of distinct values taken by the variables of the collection is greater than or equal to .
- Example
-
The constraint holds since the collection involves at least 2 distinct values (i.e.,Β in fact 4 distinct values).
- Typical
- Symmetries
can be decreased to any value .
Items of are permutable.
All occurrences of two distinct values of can be swapped; all occurrences of a value of can be renamed to any unused value.
- Remark
The constraint was first introduced by J.-C. Régin under the name in [Regin95]. Later on the constraint was introduced together with the constraint by C. Bessière et al. in a article [BessiereHebrardHnichKiziltanWalsh05] providing filtering algorithms for the constraint.
- Algorithm
[BessiereHebrardHnichKiziltanWalsh05] provides a sketch of a filtering algorithm enforcing arc-consistency for the constraint. This algorithm is based on the maximal matching in a bipartite graph.
- See also
-
implied by: Β ( replaced by ).
- Keywords
constraint type: counting constraint, value partitioning constraint.
filtering: bipartite matching, arc-consistency.
final graph structure: strongly connected component, equivalence.
modelling: number of distinct equivalence classes, number of distinct values.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph class
-
- Graph model
PartsΒ (A) andΒ (B) of FigureΒ 5.30.1 respectively show the initial and final graph associated with the Example slot. Since we use the graph property we show the different strongly connected components of the final graph. Each strongly connected component corresponds to a specific value that is assigned to some variables of the collection. The 4 following values 1, 3, 6 and 7 are used by the variables of the collection.
Figure 5.30.1. Initial and final graph of the constraint
(a) 
(b)