## 5.33. atmost1

Origin
Constraint

$\mathrm{\pi \pi \pi \pi \pi \pi }\mathtt{1}\left(\mathrm{\pi \pi ΄\pi \pi }\right)$

Synonym

$\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }\mathtt{1}$.

Argument
 $\mathrm{\pi \pi ΄\pi \pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi }-\mathrm{\pi \pi \pi \pi },\mathrm{\pi }-\mathrm{\pi \pi \pi }\right)$
Restrictions
 $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi \pi ΄\pi \pi },\left[\mathrm{\pi },\mathrm{\pi }\right]\right)$ $\mathrm{\pi \pi ΄\pi \pi }.\mathrm{\pi }\beta ₯1$
Purpose

Given a collection of set variables ${s}_{1},{s}_{2},...,{s}_{n}$ and their respective cardinality ${c}_{1},{c}_{2},...,{c}_{n}$, the $\mathrm{\pi \pi \pi \pi \pi \pi }\mathtt{1}$ constraint enforces the following two conditions:

• $\beta i\beta \left[1,n\right]:|{s}_{i}|={c}_{i}$,

• $\beta i,j\beta \left[1,n\right]\left(i.

Example
$\left(\begin{array}{c}β©\begin{array}{cc}\mathrm{\pi }-\left\{5,8\right\}\hfill & \mathrm{\pi }-2,\hfill \\ \mathrm{\pi }-\left\{5\right\}\hfill & \mathrm{\pi }-1,\hfill \\ \mathrm{\pi }-\left\{5,6,7\right\}\hfill & \mathrm{\pi }-3,\hfill \\ \mathrm{\pi }-\left\{1,4\right\}\hfill & \mathrm{\pi }-2\hfill \end{array}βͺ\hfill \end{array}\right)$

The $\mathrm{\pi \pi \pi \pi \pi \pi }\mathtt{1}$ constraint holds since:

• $|\left\{5,8\right\}|=2$, $|\left\{5\right\}|=1$, $|\left\{5,6,7\right\}|=3$, $|\left\{1,4\right\}|=2$.

• $|\left\{5,8\right\}\beta \left\{5\right\}|\beta €1$, $|\left\{5,8\right\}\beta \left\{5,6,7\right\}|\beta €1$, $|\left\{5,8\right\}\beta \left\{1,4\right\}|\beta €1$,

$|\left\{5\right\}\beta \left\{5,6,7\right\}|\beta €1$, $|\left\{5\right\}\beta \left\{1,4\right\}|\beta €1$,

$|\left\{5,6,7\right\}\beta \left\{1,4\right\}|\beta €1$.

Typical
$|\mathrm{\pi \pi ΄\pi \pi }|>1$
Symmetries
• Items of $\mathrm{\pi \pi ΄\pi \pi }$ are permutable.

• All occurrences of two distinct values of $\mathrm{\pi \pi ΄\pi \pi }.\mathrm{\pi }$ can be swapped; all occurrences of a value of $\mathrm{\pi \pi ΄\pi \pi }.\mathrm{\pi }$ can be renamed to any unused value.

Remark

When we have only two set variables the $\mathrm{\pi \pi \pi \pi \pi \pi }\mathtt{1}$ constraint was called $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }\mathtt{1}$ inΒ [HoeveSabharwal07].

Algorithm

C.Β BessiΓ¨re etΒ al. have shown inΒ [BessiereHebrardHnichWalsh04] that it is NP -hard to enforce bound consistency for the $\mathrm{\pi \pi \pi \pi \pi \pi }\mathtt{1}$ constraint. Consequently, following the first filtering algorithm from A.Β Sadler and C.Β GervetΒ [SadlerGervet01], W.-J.Β vanΒ Hoeve and A.Β Sabharwal have proposed an algorithm that enforces bound-consistency when the $\mathrm{\pi \pi \pi \pi \pi \pi }\mathtt{1}$ constraint involves only two sets variablesΒ [HoeveSabharwal07].

Keywords