Global Constraint Catalog: Camong

5.25. among_interval

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Derived from $𝚊𝚖𝚘𝚗𝚐$ .

Constraint

$𝚊𝚖𝚘𝚗𝚐_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕 (𝙽𝚅𝙰𝚁, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝙻𝙾𝚆, 𝚄𝙿)$

Arguments

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

Restrictions

𝙽𝚅𝙰𝚁 \geq 0

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝙻𝙾𝚆 \leq 𝚄𝙿

Purpose

$𝙽𝚅𝙰𝚁$ is the number of variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ taking a value that is located within interval $[𝙻𝙾𝚆, 𝚄𝙿$ ].

Example

(3, 〈4, 5, 8, 4, 1〉, 3, 5)

The $𝚊𝚖𝚘𝚗𝚐_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ constraint holds since we have 3 values, namely $4, 5$ and 4 that are situated within interval $[3, 5]$ .

Typical

𝙽𝚅𝙰𝚁 > 0

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

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

𝙻𝙾𝚆 < 𝚄𝙿

𝙻𝙾𝚆 \leq

𝚖𝚊𝚡𝚟𝚊𝚕

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

𝚄𝙿 \geq

𝚖𝚒𝚗𝚟𝚊𝚕

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

Symmetries

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are permutable.
An occurrence of a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ that belongs to $[𝙻𝙾𝚆, 𝚄𝙿]$ (resp. does not belong to $[𝙻𝙾𝚆, 𝚄𝙿]$ ) can be replaced by any other value in $[𝙻𝙾𝚆, 𝚄𝙿]$ ) (resp. not in $[𝙻𝙾𝚆, 𝚄𝙿]$ ).

Arg. properties

Functional dependency: $𝙽𝚅𝙰𝚁$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ , $𝙻𝙾𝚆$ and $𝚄𝙿$ .
Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙽𝚅𝙰𝚁 = 0$ .
Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙽𝚅𝙰𝚁 = | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |$ .
Aggregate: $𝙽𝚅𝙰𝚁 (+)$ , $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 (𝚞𝚗𝚒𝚘𝚗)$ , $𝙻𝙾𝚆 (𝚒𝚍)$ , $𝚄𝙿 (𝚒𝚍)$ .

Remark

By giving explicitly all values of the interval $[𝙻𝙾𝚆, 𝚄𝙿]$ the $𝚊𝚖𝚘𝚗𝚐_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ constraint can be modelled with the $𝚊𝚖𝚘𝚗𝚐$ constraint. However when $𝙻𝙾𝚆 - 𝚄𝙿 + 1$ is a large quantity the $𝚊𝚖𝚘𝚗𝚐_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ constraint provides a more compact form.

See also

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

Keywords

characteristic of a constraint: automaton, automaton with counters.

constraint arguments: pure functional dependency.

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

constraint type: value constraint, counting constraint.

filtering: arc-consistency.

modelling: interval, functional dependency.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝑆𝐸𝐿𝐹

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

Arc arity

Arc constraint(s)

• 𝙻𝙾𝚆 \leq 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚟𝚊𝚛

• 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚟𝚊𝚛 \leq 𝚄𝙿

Graph property(ies)

𝐍𝐀𝐑𝐂

= 𝙽𝚅𝙰𝚁

Graph model

The arc constraint corresponds to a unary constraint. For this reason 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.25.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.25.1. Initial and final graph of the $𝚊𝚖𝚘𝚗𝚐_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ constraint


(a)	(b)

Automaton: Figure 5.25.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}$ : $𝙻𝙾𝚆 \leq {𝚅𝙰𝚁}_{i} \land {𝚅𝙰𝚁}_{i} \leq 𝚄𝙿 \Leftrightarrow S_{i}$ . The automaton counts the number of variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection that take their value in $[𝙻𝙾𝚆, 𝚄𝙿$ ] and finally assigns this number to $𝙽𝚅𝙰𝚁$ .

Figure 5.25.2. Automaton of the $𝚊𝚖𝚘𝚗𝚐_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ constraint

Figure 5.25.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.25. among_interval

Figure 5.25.1. Initial and final graph of the $𝚊𝚖𝚘𝚗𝚐_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ constraint

Figure 5.25.2. Automaton of the $𝚊𝚖𝚘𝚗𝚐_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.25. among_interval

Figure 5.25.1. Initial and final graph of the 𝚊𝚖𝚘𝚗𝚐_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕 constraint

Figure 5.25.2. Automaton of the 𝚊𝚖𝚘𝚗𝚐_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕 constraint

Figure 5.25.1. Initial and final graph of the $𝚊𝚖𝚘𝚗𝚐_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ constraint

Figure 5.25.2. Automaton of the $𝚊𝚖𝚘𝚗𝚐_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ constraint