## 5.33. atmost1

Origin
Constraint

$\mathrm{𝚊𝚝𝚖𝚘𝚜𝚝}\mathtt{1}\left(\mathrm{𝚂𝙴𝚃𝚂}\right)$

Synonym

$\mathrm{𝚙𝚊𝚒𝚛}_\mathrm{𝚊𝚝𝚖𝚘𝚜𝚝}\mathtt{1}$.

Argument
 $\mathrm{𝚂𝙴𝚃𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(𝚜-\mathrm{𝚜𝚟𝚊𝚛},𝚌-\mathrm{𝚒𝚗𝚝}\right)$
Restrictions
 $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚂𝙴𝚃𝚂},\left[𝚜,𝚌\right]\right)$ $\mathrm{𝚂𝙴𝚃𝚂}.𝚌\ge 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{𝚊𝚝𝚖𝚘𝚜𝚝}\mathtt{1}$ constraint enforces the following two conditions:

• $\forall i\in \left[1,n\right]:|{s}_{i}|={c}_{i}$,

• $\forall i,j\in \left[1,n\right]\left(i.

Example
$\left(\begin{array}{c}〈\begin{array}{cc}𝚜-\left\{5,8\right\}\hfill & 𝚌-2,\hfill \\ 𝚜-\left\{5\right\}\hfill & 𝚌-1,\hfill \\ 𝚜-\left\{5,6,7\right\}\hfill & 𝚌-3,\hfill \\ 𝚜-\left\{1,4\right\}\hfill & 𝚌-2\hfill \end{array}〉\hfill \end{array}\right)$

The $\mathrm{𝚊𝚝𝚖𝚘𝚜𝚝}\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\}\bigcap \left\{5\right\}|\le 1$, $|\left\{5,8\right\}\bigcap \left\{5,6,7\right\}|\le 1$, $|\left\{5,8\right\}\bigcap \left\{1,4\right\}|\le 1$,

$|\left\{5\right\}\bigcap \left\{5,6,7\right\}|\le 1$, $|\left\{5\right\}\bigcap \left\{1,4\right\}|\le 1$,

$|\left\{5,6,7\right\}\bigcap \left\{1,4\right\}|\le 1$.

Typical
$|\mathrm{𝚂𝙴𝚃𝚂}|>1$
Symmetries
• Items of $\mathrm{𝚂𝙴𝚃𝚂}$ are permutable.

• All occurrences of two distinct values of $\mathrm{𝚂𝙴𝚃𝚂}.𝚜$ can be swapped; all occurrences of a value of $\mathrm{𝚂𝙴𝚃𝚂}.𝚜$ can be renamed to any unused value.

Remark

When we have only two set variables the $\mathrm{𝚊𝚝𝚖𝚘𝚜𝚝}\mathtt{1}$ constraint was called $\mathrm{𝚙𝚊𝚒𝚛}_\mathrm{𝚊𝚝𝚖𝚘𝚜𝚝}\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{𝚊𝚝𝚖𝚘𝚜𝚝}\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{𝚊𝚝𝚖𝚘𝚜𝚝}\mathtt{1}$ constraint involves only two sets variables [HoeveSabharwal07].

Keywords