## 5.37. atleast_nvalue

Origin
Constraint

$\mathrm{\pi \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)$

Synonym

$\mathrm{\pi }_\mathrm{\pi \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 \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)$ $\mathrm{\pi ½\pi  \pi °\pi »}\beta ₯0$ $\mathrm{\pi ½\pi  \pi °\pi »}\beta €|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$ $\mathrm{\pi ½\pi  \pi °\pi »}\beta €$$\mathrm{\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 greater than or equal to $\mathrm{\pi ½\pi  \pi °\pi »}$.

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

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

Typical
 $\mathrm{\pi ½\pi  \pi °\pi »}>0$ $\mathrm{\pi ½\pi  \pi °\pi »}<|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$ $\mathrm{\pi ½\pi  \pi °\pi »}<$$\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)$ $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>1$
Symmetries
• $\mathrm{\pi ½\pi  \pi °\pi »}$ can be decreased to any value $\beta ₯0$.

• 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.

Arg. properties

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

Remark

The $\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint was first introduced by J.-C.Β RΓ©gin under the name $\mathrm{\pi }_\mathrm{\pi \pi \pi \pi }$ inΒ [Regin95]. Later on the $\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint was introduced together with the $\mathrm{\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.

Algorithm

[BessiereHebrardHnichKiziltanWalsh05] provides a sketch of a filtering algorithm enforcing arc-consistency for the $\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint. This algorithm is based on the maximal matching in a bipartite graph.

Counting
 Length ($n$) 2 3 4 5 6 7 8 Solutions 24 212 2470 35682 614600 12286024 279472266

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

Length ($n$)2345678
Total2421224703568261460012286024279472266
 Parameter value

09646257776117649209715243046721
19646257776117649209715243046721
26606207770117642209714443046712
3-244807320116340209361643037568
4--120432097440199248042550704
5---72042840140448037406880
6----504046368021530880
7-----403205443200
8------362880

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

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.37.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 4 following values 1, 3, 6 and 7 are used by the variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection.