## 5.41. atmost_nvalue

Origin
Constraint

$\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi ½\pi  \pi °\pi »},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$

Synonyms

$\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi ‘}_\mathrm{\pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi ‘}_\mathrm{\pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi ‘}_\mathrm{\pi \pi \pi }$.

Arguments
 $\mathrm{\pi ½\pi  \pi °\pi »}$ $\mathrm{\pi \pi \pi \pi }$ $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$
Restrictions
 $\mathrm{\pi ½\pi  \pi °\pi »}\beta ₯\mathrm{\pi \pi \pi }\left(1,|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|\right)$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)$
Purpose

The number of distinct values taken by the variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ is less than or equal to $\mathrm{\pi ½\pi  \pi °\pi »}$.

Example
 $\left(4,β©3,1,3,1,6βͺ\right)$ $\left(3,β©3,1,3,1,6βͺ\right)$ $\left(1,β©3,3,3,3,3βͺ\right)$

The first $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint holds since the collection $\beta ©3,1,3,1,6\beta ͺ$ involves at most 4 distinct values (i.e.,Β in fact 3 distinct values).

Typical
 $\mathrm{\pi ½\pi  \pi °\pi »}>1$ $\mathrm{\pi ½\pi  \pi °\pi »}<|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$ $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>1$
Symmetries
• $\mathrm{\pi ½\pi  \pi °\pi »}$ can be increased.

• Items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ are permutable.

• All occurrences of two distinct values of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }$ can be swapped; all occurrences of a value of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }$ can be renamed to any unused value.

• An occurrence of a value of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }$ can be replaced by any value of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }$.

Arg. properties

Contractible wrt. $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

Remark

This constraint was introduced together with the $\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint by C.Β BessiΓ¨re et al. in an articleΒ [BessiereHebrardHnichKiziltanWalsh05] providing filtering algorithms for the $\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint.

It was shown inΒ [BessiereHebrardHnichWalshO4] that, finding out whether a $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$ 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.

Counting
 Length ($n$) 2 3 4 5 6 7 8 Solutions 12 108 1280 18750 326592 6588344 150994944

Number of solutions for $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$: domains $0..n$

Length ($n$)2345678
Total121081280187503265926588344150994944
 Parameter value

13456789
2940145456130935369153
3-64505345620209104672496017
4--6257056748096926725639841
5---7776112609163347221515841
6----117649205683237603521
7-----209715242683841
8------43046721

Solution count for $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$: domains $0..n$

Systems

implied by: $\mathrm{\pi \pi \pi \pi \pi \pi }$Β ($\beta €$ $\mathrm{\pi ½\pi  \pi °\pi »}$ replaced by $=$ $\mathrm{\pi ½\pi  \pi °\pi »}$).

Keywords
Arc input(s)

$\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$

Arc generator
$\mathrm{\pi Ά\pi Ώ\pi Ό\pi \pi \pi Έ}$$\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1},\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi }=\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi }$
Graph property(ies)
$\mathrm{\pi \pi \pi \pi }$$\beta €\mathrm{\pi ½\pi  \pi °\pi »}$

Graph class
$\mathrm{\pi ΄\pi \pi \pi Έ\pi  \pi °\pi »\pi ΄\pi ½\pi ²\pi ΄}$

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.41.1 respectively show the initial and final graph associated with the first example of the Example slot. Since we use the $\mathrm{\pi \pi \pi \pi }$ 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 $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection. The 3 following values 1, 3 and 6 are used by the variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection.