Global Constraint Catalog: Catmost1

5.40. atmost1

DESCRIPTION

LINKS

Origin

[SadlerGervet01]

Constraint

$𝚊𝚝𝚖𝚘𝚜𝚝 1 (𝚂𝙴𝚃𝚂)$

Synonym

$𝚙𝚊𝚒𝚛_𝚊𝚝𝚖𝚘𝚜𝚝 1$ .

Argument

𝚂𝙴𝚃𝚂

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚜 - 𝚜𝚟𝚊𝚛, 𝚌 - 𝚒𝚗𝚝)

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚂𝙴𝚃𝚂, [𝚜, 𝚌])

𝚂𝙴𝚃𝚂 . 𝚌 \geq 1

Purpose

Given a collection of set variables $s_{1}, s_{2}, \dots, s_{n}$ and their respective cardinality $c_{1}, c_{2}, \dots, c_{n}$ , the $𝚊𝚝𝚖𝚘𝚜𝚝 1$ constraint forces the following two conditions:

$\forall i \in [1, n] : | s_{i} | = c_{i}$ ,
$\forall i, j \in [1, n] (i < j) : | s_{i} ⋂ s_{j} | \leq 1$ .

Example

(\begin{matrix} 〈\begin{matrix} 𝚜 - {5, 8} & 𝚌 - 2, \\ 𝚜 - {5} & 𝚌 - 1, \\ 𝚜 - {5, 6, 7} & 𝚌 - 3, \\ 𝚜 - {1, 4} & 𝚌 - 2 \end{matrix}〉 \end{matrix})

The $𝚊𝚝𝚖𝚘𝚜𝚝 1$ constraint holds since:

$| {5, 8} | = 2$ , $| {5} | = 1$ , $| {5, 6, 7} | = 3$ , $| {1, 4} | = 2$ .
$| {5, 8} ⋂ {5} | \leq 1$ , $| {5, 8} ⋂ {5, 6, 7} | \leq 1$ , $| {5, 8} ⋂ {1, 4} | \leq 1$ ,

$| {5} ⋂ {5, 6, 7} | \leq 1$ , $| {5} ⋂ {1, 4} | \leq 1$ ,

$| {5, 6, 7} ⋂ {1, 4} | \leq 1$ .

Typical

| 𝚂𝙴𝚃𝚂 | > 1

Symmetries

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.

Arg. properties

Contractible wrt. $𝚂𝙴𝚃𝚂$ .

Remark

When we have only two set variables the $𝚊𝚝𝚖𝚘𝚜𝚝 1$ constraint was called $𝚙𝚊𝚒𝚛_𝚊𝚝𝚖𝚘𝚜𝚝 1$ in [HoeveSabharwal07].

Algorithm

C. Bessière et al. have shown in [BessiereHebrardHnichWalsh04] that it is NP-hard to enforce bound consistency for the $𝚊𝚝𝚖𝚘𝚜𝚝 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 $𝚊𝚝𝚖𝚘𝚜𝚝 1$ constraint involves only two sets variables [HoeveSabharwal07].

Systems

at_most1 in MiniZinc.

Keywords

constraint arguments: constraint involving set variables.

constraint type: predefined constraint.

filtering: bound-consistency.

Global Constraint Catalog

5. Global Constraint Catalogue

5.40. atmost1