Global Constraint Catalog: Catmost

5.39. atmost

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

CHIP

Constraint

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

Synonym

$𝚌𝚘𝚞𝚗𝚝$ .

Arguments

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

Restrictions

𝙽 \geq 0

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

Purpose

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

Example

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

The $𝚊𝚝𝚖𝚘𝚜𝚝$ constraint holds since at most 1 value of the collection $〈 4, 2, 4, 5 〉$ is equal to value 2.

All solutions

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

Figure 5.39.1. All solutions corresponding to the non ground example of the $𝚊𝚝𝚖𝚘𝚜𝚝$ constraint of the All solutions slot

Typical

𝙽 > 0

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

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

𝚊𝚝𝚕𝚎𝚊𝚜𝚝

(1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚅𝙰𝙻𝚄𝙴)

Symmetries

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

Arg. properties

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

Systems

occurenceMax in Choco, count in Gecode, atmost in Gecode, count in JaCoP, at_most in MiniZinc, count in SICStus.

comparison swapped: $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ .

generalisation: $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ replaced by $𝚝𝚊𝚜𝚔$ ).

implied by: $𝚎𝚡𝚊𝚌𝚝𝚕𝚢$ ( $\leq$ $𝙽$ 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 most.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝑆𝐸𝐿𝐹

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

Arc arity

Arc constraint(s)

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

Graph property(ies)

𝐍𝐀𝐑𝐂

\leq 𝙽

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.39.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.39.2. Initial and final graph of the $𝚊𝚝𝚖𝚘𝚜𝚝$ constraint


(a)	(b)

Automaton: Figure 5.39.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 less than or equal to $𝙽$ .

Figure 5.39.3. Automaton of the $𝚊𝚝𝚖𝚘𝚜𝚝$ constraint

Figure 5.39.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.39. atmost

Figure 5.39.1. All solutions corresponding to the non ground example of the $𝚊𝚝𝚖𝚘𝚜𝚝$ constraint of the All solutions slot

Figure 5.39.2. Initial and final graph of the $𝚊𝚝𝚖𝚘𝚜𝚝$ constraint

Figure 5.39.3. Automaton of the $𝚊𝚝𝚖𝚘𝚜𝚝$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.39. atmost

Figure 5.39.1. All solutions corresponding to the non ground example of the 𝚊𝚝𝚖𝚘𝚜𝚝 constraint of the All solutions slot

Figure 5.39.2. Initial and final graph of the 𝚊𝚝𝚖𝚘𝚜𝚝 constraint

Figure 5.39.3. Automaton of the 𝚊𝚝𝚖𝚘𝚜𝚝 constraint

Figure 5.39.1. All solutions corresponding to the non ground example of the $𝚊𝚝𝚖𝚘𝚜𝚝$ constraint of the All solutions slot

Figure 5.39.2. Initial and final graph of the $𝚊𝚝𝚖𝚘𝚜𝚝$ constraint

Figure 5.39.3. Automaton of the $𝚊𝚝𝚖𝚘𝚜𝚝$ constraint