Global Constraint Catalog: Catleast

5.29. atleast

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

CHIP

Constraint

$𝚊𝚝𝚕𝚎𝚊𝚜𝚝 (𝙽, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚅𝙰𝙻𝚄𝙴)$

Synonym

$𝚌𝚘𝚞𝚗𝚝$ .

Arguments

$𝙽$	$𝚒𝚗𝚝$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝚅𝙰𝙻𝚄𝙴$	$𝚒𝚗𝚝$

Restrictions

𝙽 \geq 0

𝙽 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟𝚊𝚛)

Purpose

At least $𝙽$ variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection are assigned value $𝚅𝙰𝙻𝚄𝙴$ .

Example

(2, 〈4, 2, 4, 5〉, 4)

The $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint holds since at least 2 values of the collection $〈 4, 2, 4, 5 〉$ are equal to value 4.

Typical

𝙽 > 0

𝙽 < | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > 1

Symmetries

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are permutable.
$𝙽$ can be decreased to any value $\geq 0$ .
An occurrence of a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ that is different from $𝚅𝙰𝙻𝚄𝙴$ can be replaced by any other value.

Systems

occurenceMin in Choco, count in Gecode, count in JaCoP, count in SICStus.

Used in

$𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚎𝚡𝚌𝚎𝚙𝚝_0$ , $𝚊𝚖𝚘𝚗𝚐_𝚍𝚒𝚏𝚏_0$ , $𝚒𝚗𝚝_𝚟𝚊𝚕𝚞𝚎_𝚙𝚛𝚎𝚌𝚎𝚍𝚎$ , $𝚒𝚝𝚑_𝚙𝚘𝚜_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚏𝚛𝚘𝚖_0$ .

comparison swapped: $𝚊𝚝𝚖𝚘𝚜𝚝$ .

implied by: $𝚎𝚡𝚊𝚌𝚝𝚕𝚢$ ( $\geq$ $𝙽$ replaced by $=$ $𝙽$ ).

related: $𝚛𝚘𝚘𝚝𝚜$ .

soft variant: $𝚘𝚙𝚎𝚗_𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ (open constraint).

Keywords

characteristic of a constraint: automaton, automaton with counters.

constraint network structure: alpha-acyclic constraint network(2).

constraint type: value constraint.

filtering: arc-consistency.

modelling: at least.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝑆𝐸𝐿𝐹

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜)

Arc arity

Arc constraint(s)

𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚟𝚊𝚛 = 𝚅𝙰𝙻𝚄𝙴

Graph property(ies)

𝐍𝐀𝐑𝐂

\geq 𝙽

Graph model

Since each arc constraint involves only one vertex ( $𝚅𝙰𝙻𝚄𝙴$ is fixed), we employ the $𝑆𝐸𝐿𝐹$ arc generator in order to produce a graph with a single loop on each vertex.

Parts (A) and (B) of Figure 5.29.1 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐍𝐀𝐑𝐂$ graph property, the loops of the final graph are stressed in bold.

Figure 5.29.1. Initial and final graph of the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint


(a)	(b)

Automaton: Figure 5.29.2 depicts the automaton associated with the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint. To each variable ${𝚅𝙰𝚁}_{i}$ of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ corresponds a 0-1 signature variable $𝚂_{i}$ . The following signature constraint links ${𝚅𝙰𝚁}_{i}$ and $𝚂_{i}$ : ${𝚅𝙰𝚁}_{i} = 𝚅𝙰𝙻𝚄𝙴 \Leftrightarrow 𝚂_{i}$ . The automaton counts the number of variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection that are assigned value $𝚅𝙰𝙻𝚄𝙴$ and finally checks that this number is greater than or equal to $𝙽$ .

Figure 5.29.2. Automaton of the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint

Figure 5.29.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.29. atleast

Figure 5.29.1. Initial and final graph of the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint

Figure 5.29.2. Automaton of the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint

Figure 5.29.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint

W3C: XHTML - last update: 2010-12-6. SD.

Global Constraint Catalog

5. Global Constraint Catalogue

5.29. atleast

Figure 5.29.1. Initial and final graph of the 𝚊𝚝𝚕𝚎𝚊𝚜𝚝 constraint

Figure 5.29.2. Automaton of the 𝚊𝚝𝚕𝚎𝚊𝚜𝚝 constraint

Figure 5.29.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚊𝚝𝚕𝚎𝚊𝚜𝚝 constraint

W3C: XHTML - last update: 2010-12-6. SD.

Figure 5.29.1. Initial and final graph of the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint

Figure 5.29.2. Automaton of the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint

Figure 5.29.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint