Global Constraint Catalog: Ccardinality

5.59. cardinality_atmost

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Derived from $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ .

Constraint

$𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚊𝚝𝚖𝚘𝚜𝚝 (𝙰𝚃𝙼𝙾𝚂𝚃, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚅𝙰𝙻𝚄𝙴𝚂)$

Arguments

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

Restrictions

𝙰𝚃𝙼𝙾𝚂𝚃 \geq 0

𝙰𝚃𝙼𝙾𝚂𝚃 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝙻𝚄𝙴𝚂, 𝚟𝚊𝚕)

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

(𝚅𝙰𝙻𝚄𝙴𝚂, 𝚟𝚊𝚕)

Purpose

$𝙰𝚃𝙼𝙾𝚂𝚃$ is the maximum number of occurrences of each value of $𝚅𝙰𝙻𝚄𝙴𝚂$ within the variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Example

(2, 〈2, 1, 7, 1, 2〉, 〈5, 7, 2, 9〉)

In this example, values 5, 7, 2 and 9 occur respectively 0, 1, 2 and 0 times within the collection $〈 2, 1, 7, 1, 2 〉$ . As a consequence, the $𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚊𝚝𝚖𝚘𝚜𝚝$ constraint holds since its first argument $𝙰𝚃𝙼𝙾𝚂𝚃$ is assigned to the maximum number of occurrences 2.

Typical

𝙰𝚃𝙼𝙾𝚂𝚃 > 0

𝙰𝚃𝙼𝙾𝚂𝚃 < | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

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

| 𝚅𝙰𝙻𝚄𝙴𝚂 | > 0

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

Symmetries

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are permutable.
Items of $𝚅𝙰𝙻𝚄𝙴𝚂$ are permutable.
An occurrence of a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ that does not belong to $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ can be replaced by any other value that also does not belong to $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ .
All occurrences of two distinct values in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ or $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ can be swapped; all occurrences of a value in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ or $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ can be renamed to any unused value.

Arg. properties

Functional dependency: $𝙰𝚃𝙼𝙾𝚂𝚃$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ and $𝚅𝙰𝙻𝚄𝙴𝚂$ .

Usage

An application of the $𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚊𝚝𝚖𝚘𝚜𝚝$ constraint is to enforce a maximum use of values.

Remark

This is a restricted form of a variant of the $𝚊𝚖𝚘𝚗𝚐$ constraint and of the $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ constraint. In the original $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ constraint, one specifies for each value its minimum and maximum number of occurrences.

Algorithm

See $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ [Regin96].

See also

generalisation: $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ (single $𝚌𝚘𝚞𝚗𝚝 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ replaced by an individual $𝚌𝚘𝚞𝚗𝚝 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ for each value), $𝚖𝚞𝚕𝚝𝚒_𝚒𝚗𝚝𝚎𝚛_𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎$ (window of size 1 replaced by window of $𝙳𝙸𝚂𝚃$ consecutive values).

implied by: $𝚊𝚖𝚘𝚗𝚐$ .

Keywords

application area: assignment.

characteristic of a constraint: automaton, automaton with array of counters.

constraint arguments: pure functional dependency.

constraint type: value constraint.

filtering: arc-consistency.

final graph structure: acyclic, bipartite, no loop.

modelling: at most, functional dependency.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ $𝚅𝙰𝙻𝚄𝙴𝚂$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚟𝚊𝚛 = 𝚟𝚊𝚕𝚞𝚎𝚜 . 𝚟𝚊𝚕

Graph property(ies)

𝐌𝐀𝐗_𝐈𝐃

= 𝙰𝚃𝙼𝙾𝚂𝚃

Graph class

•

𝙰𝙲𝚈𝙲𝙻𝙸𝙲

•

𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴

•

𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

Parts (A) and (B) of Figure 5.59.1 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐌𝐀𝐗_𝐈𝐃$ graph property, the vertex that has the maximum number of predecessor is stressed with a double circle.

Figure 5.59.1. Initial and final graph of the $𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚊𝚝𝚖𝚘𝚜𝚝$ constraint


(a)	(b)

Automaton: Figure 5.59.2 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} \in 𝚅𝙰𝙻𝚄𝙴𝚂 \Leftrightarrow S_{i}$ .

Figure 5.59.2. Automaton of the $𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚊𝚝𝚖𝚘𝚜𝚝$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.59. cardinality_atmost

Figure 5.59.1. Initial and final graph of the $𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚊𝚝𝚖𝚘𝚜𝚝$ constraint

Figure 5.59.2. Automaton of the $𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚊𝚝𝚖𝚘𝚜𝚝$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.59. cardinality_atmost

Figure 5.59.1. Initial and final graph of the 𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚊𝚝𝚖𝚘𝚜𝚝 constraint

Figure 5.59.2. Automaton of the 𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚊𝚝𝚖𝚘𝚜𝚝 constraint

Figure 5.59.1. Initial and final graph of the $𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚊𝚝𝚖𝚘𝚜𝚝$ constraint

Figure 5.59.2. Automaton of the $𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚊𝚝𝚖𝚘𝚜𝚝$ constraint