Global Constraint Catalog: Catleast

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

All solutions

Figure 5.36.1 gives all solutions to the following non ground instance of the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint: $V_{1} \in [3, 5]$ , $V_{2} \in [1, 2]$ , $V_{3} \in [5, 6]$ , $V_{4} \in [7, 9]$ , $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ $(2, 〈 V_{1}, V_{2}, V_{3}, V_{4} 〉, 5)$ .

Figure 5.36.1. All solutions corresponding to the non ground example of the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint of the All solutions slot

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.

Arg. properties

Extensible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Systems

occurenceMin in Choco, count in Gecode, atleast in Gecode, count in JaCoP, at_least in MiniZinc, count in SICStus.

Used in

$𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚎𝚡𝚌𝚎𝚙𝚝_0$ , $𝚊𝚖𝚘𝚗𝚐_𝚍𝚒𝚏𝚏_0$ , $𝚊𝚝𝚖𝚘𝚜𝚝$ , $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚘𝚗𝚝𝚒𝚐𝚞𝚒𝚝𝚢$ , $𝚒𝚗𝚝_𝚟𝚊𝚕𝚞𝚎_𝚙𝚛𝚎𝚌𝚎𝚍𝚎$ , $𝚒𝚝𝚑_𝚙𝚘𝚜_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚏𝚛𝚘𝚖_0$ , $𝚖𝚒𝚗𝚒𝚖𝚞𝚖_𝚎𝚡𝚌𝚎𝚙𝚝_0$ , $𝚗𝚟𝚊𝚕𝚞𝚎𝚜_𝚎𝚡𝚌𝚎𝚙𝚝_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.36.2 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.36.2. Initial and final graph of the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint


(a)	(b)

Automaton: Figure 5.36.3 depicts the automaton associated with the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint. To each variable ${𝚅𝙰𝚁}_{i}$ of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ corresponds a 0-1 signature variable $S_{i}$ . The following signature constraint links ${𝚅𝙰𝚁}_{i}$ and $S_{i}$ : ${𝚅𝙰𝚁}_{i} = 𝚅𝙰𝙻𝚄𝙴 \Leftrightarrow S_{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.36.3. Automaton of the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint

Figure 5.36.4. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint: since all states variables $Q_{0}, Q_{1}, \dots, Q_{n}$ are fixed to the unique state $s$ of the automaton, the transitions constraints share only the counter variable $C$ and the constraint network is Berge-acyclic

Global Constraint Catalog

5. Global Constraint Catalogue

5.36. atleast

Figure 5.36.1. All solutions corresponding to the non ground example of the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint of the All solutions slot

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

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

Global Constraint Catalog

5. Global Constraint Catalogue

5.36. atleast

Figure 5.36.1. All solutions corresponding to the non ground example of the 𝚊𝚝𝚕𝚎𝚊𝚜𝚝 constraint of the All solutions slot

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

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

Figure 5.36.1. All solutions corresponding to the non ground example of the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ constraint of the All solutions slot

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

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