5.34. atmost_nvalue
| DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Synonyms
, , .
- Arguments
- Restrictions
- Purpose
The number of distinct values taken by the variables of the collection is less than or equal to .
- Example
-
The constraint holds since the collection involves at most 4 distinct values (i.e.,Β in fact 3 distinct values).
- Typical
- Symmetries
can be increased.
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.
An occurrence of a value of can be replaced by any value of .
- Remark
This constraint was introduced together with the constraint by C. Bessière et al. in a article [BessiereHebrardHnichKiziltanWalsh05] providing filtering algorithms for the constraint.
It was shown inΒ [BessiereHebrardHnichWalshO4] that, finding out whether a constraint has a solution or not is NP-hard. This was achieved by reduction from 3-SAT.
- Algorithm
[Beldiceanu01] provides an algorithm that achieves bound consistency. [BeldiceanuCarlssonThiel02] provides two filtering algorithms, whileΒ [BessiereHebrardHnichKiziltanWalsh05] provides a greedy algorithm and a graph invariant for evaluating the minimum number of distinct values. [BessiereHebrardHnichKiziltanWalsh05] also gives a linear relaxation for approximating the minimum number of distinct values.
- Systems
atMostNValue in Choco.
- See also
-
implied by: Β ( replaced by ).
related: , , , , .
- Keywords
-
constraint type: counting constraint, value partitioning constraint.
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.34.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 3 following values 1, 3 and 6 are used by the variables of the collection.
Figure 5.34.1. Initial and final graph of the constraint
(a) 
(b)