Global Constraint Catalog: Cexactly

5.155. exactly

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Derived from $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ and $𝚊𝚝𝚖𝚘𝚜𝚝$ .

Constraint

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

Synonym

$𝚌𝚘𝚞𝚗𝚝$ .

Arguments

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

Restrictions

𝙽 \geq 0

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

Purpose

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

Example

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

The $𝚎𝚡𝚊𝚌𝚝𝚕𝚢$ constraint holds since exactly $𝙽 = 2$ variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 = 〈 4, 2, 4, 5 〉$ collection are assigned value $𝚅𝙰𝙻𝚄𝙴 = 4$ .

Typical

𝙽 > 0

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

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

Symmetries

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

Arg. properties

Functional dependency: $𝙽$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ and $𝚅𝙰𝙻𝚄𝙴$ .
Aggregate: $𝙽 (+)$ , $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 (𝚞𝚗𝚒𝚘𝚗)$ , $𝚅𝙰𝙻𝚄𝙴 (𝚒𝚍)$ .

Systems

occurence in Choco, count in Gecode, exactly in Gecode, count in JaCoP, exactly in MiniZinc, count in SICStus.

See also

generalisation: $𝚊𝚖𝚘𝚗𝚐$ ( $𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ and $𝚟𝚊𝚕𝚞𝚎$ replaced by $𝚕𝚒𝚜𝚝$ of $𝚟𝚊𝚕𝚞𝚎𝚜$ ).

implies: $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ ( $= 𝙽$ replaced by $\geq 𝙽$ ), $𝚊𝚝𝚖𝚘𝚜𝚝$ ( $= 𝙽$ replaced by $\leq 𝙽$ ).

Keywords

characteristic of a constraint: automaton, automaton with counters.

constraint arguments: reverse of a constraint, pure functional dependency.

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

constraint type: value constraint, counting constraint.

filtering: glue matrix, arc-consistency.

modelling: functional dependency.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝑆𝐸𝐿𝐹

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

Arc arity

Arc constraint(s)

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

Graph property(ies)

𝐍𝐀𝐑𝐂

= 𝙽

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.155.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. The $𝚎𝚡𝚊𝚌𝚝𝚕𝚢$ constraint holds since exactly two variables are assigned value 4.

Figure 5.155.1. Initial and final graph of the $𝚎𝚡𝚊𝚌𝚝𝚕𝚢$ constraint


(a)	(b)

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

Figure 5.155.2. Automaton (with one counter) of the $𝚎𝚡𝚊𝚌𝚝𝚕𝚢$ constraint and its glue matrix

Figure 5.155.3. 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.155. exactly

Figure 5.155.1. Initial and final graph of the $𝚎𝚡𝚊𝚌𝚝𝚕𝚢$ constraint

Figure 5.155.2. Automaton (with one counter) of the $𝚎𝚡𝚊𝚌𝚝𝚕𝚢$ constraint and its glue matrix

Global Constraint Catalog

5. Global Constraint Catalogue

5.155. exactly

Figure 5.155.1. Initial and final graph of the 𝚎𝚡𝚊𝚌𝚝𝚕𝚢 constraint

Figure 5.155.2. Automaton (with one counter) of the 𝚎𝚡𝚊𝚌𝚝𝚕𝚢 constraint and its glue matrix

Figure 5.155.1. Initial and final graph of the $𝚎𝚡𝚊𝚌𝚝𝚕𝚢$ constraint

Figure 5.155.2. Automaton (with one counter) of the $𝚎𝚡𝚊𝚌𝚝𝚕𝚢$ constraint and its glue matrix