Global Constraint Catalog: Camong_low

5.26. among_low_up

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

[BeldiceanuContejean94]

Constraint

$𝚊𝚖𝚘𝚗𝚐_𝚕𝚘𝚠_𝚞𝚙 (𝙻𝙾𝚆, 𝚄𝙿, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚅𝙰𝙻𝚄𝙴𝚂)$

Arguments

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

Restrictions

𝙻𝙾𝚆 \geq 0

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

𝚄𝙿 \geq 0

𝚄𝙿 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝚄𝙿 \geq 𝙻𝙾𝚆

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

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

Purpose

Between $𝙻𝙾𝚆$ and $𝚄𝙿$ variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection are assigned a value of the $𝚅𝙰𝙻𝚄𝙴𝚂$ collection.

Example

(1, 2, 〈9, 2, 4, 5〉, 〈0, 2, 4, 6, 8〉)

The $𝚊𝚖𝚘𝚗𝚐_𝚕𝚘𝚠_𝚞𝚙$ constraint holds since between 1 and 2 values (i.e., in fact 2 values) of the collection of values $〈 9, 2, 4, 5 〉$ belong to the set of values ${0, 2, 4, 6, 8}$ .

Typical

𝙻𝙾𝚆 < | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝚄𝙿 > 0

𝙻𝙾𝚆 < 𝚄𝙿

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

| 𝚅𝙰𝙻𝚄𝙴𝚂 | > 1

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

𝙻𝙾𝚆 > 0 \lor 𝚄𝙿 < | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

Symmetries

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are permutable.
Items of $𝚅𝙰𝙻𝚄𝙴𝚂$ are permutable.
$𝙻𝙾𝚆$ can be decreased to any value $\geq 0$ .
$𝚄𝙿$ can be increased to any value $\leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |$ .
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

Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝚄𝙿 = 0$ .
Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝚄𝙿 = | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |$ .
Aggregate: $𝙻𝙾𝚆 (+)$ , $𝚄𝙿 (+)$ , $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 (𝚞𝚗𝚒𝚘𝚗)$ , $𝚅𝙰𝙻𝚄𝙴𝚂 (𝚜𝚞𝚗𝚒𝚘𝚗)$ .

Algorithm

The $𝚊𝚖𝚘𝚗𝚐_𝚕𝚘𝚠_𝚞𝚙$ constraint is entailed if and only if the following two conditions hold:

The number of variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection assigned a value of the $𝚅𝙰𝙻𝚄𝙴𝚂$ collection is greater than or equal to $𝙻𝙾𝚆$ .
The number of variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection that can potentially be assigned a value of the $𝚅𝙰𝙻𝚄𝙴𝚂$ collection is less than or equal to $𝚄𝙿$ .

Used in

$𝚊𝚖𝚘𝚗𝚐_𝚜𝚎𝚚$ , $𝚌𝚢𝚌𝚕𝚎_𝚌𝚊𝚛𝚍_𝚘𝚗_𝚙𝚊𝚝𝚑$ , $𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝$ , $𝚜𝚕𝚒𝚍𝚒𝚗𝚐_𝚌𝚊𝚛𝚍_𝚜𝚔𝚒𝚙 0$ .

generalisation: $𝚊𝚖𝚘𝚗𝚐$ ( $𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ ), $𝚜𝚕𝚒𝚍𝚒𝚗𝚐_𝚌𝚊𝚛𝚍_𝚜𝚔𝚒𝚙 0$ (full sequence replaced by maximal sequences of non-zeros).

system of constraints: $𝚊𝚖𝚘𝚗𝚐_𝚜𝚎𝚚$ .

Keywords

characteristic of a constraint: automaton, automaton with counters.

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

constraint type: value constraint, counting constraint.

filtering: arc-consistency, entailment.

final graph structure: acyclic, bipartite, no loop.

Cond. implications

$𝚊𝚖𝚘𝚗𝚐_𝚕𝚘𝚠_𝚞𝚙 (𝙻𝙾𝚆, 𝚄𝙿, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚅𝙰𝙻𝚄𝙴𝚂)$

with $𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟𝚊𝚛)$

implies $𝚊𝚖𝚘𝚗𝚐_𝚕𝚘𝚠_𝚞𝚙 (𝙻𝙾𝚆, 𝚄𝙿, 𝚅𝙰𝙻𝚄𝙴𝚂, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ .

Arc input(s)

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

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

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

Graph property(ies)

•

𝐍𝐀𝐑𝐂

\geq 𝙻𝙾𝚆

•

𝐍𝐀𝐑𝐂

\leq 𝚄𝙿

Graph class

•

𝙰𝙲𝚈𝙲𝙻𝙸𝙲

•

𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴

•

𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

Each arc constraint of the final graph corresponds to the fact that a variable is assigned to a value that belong to the $𝚅𝙰𝙻𝚄𝙴𝚂$ collection. The two graph properties restrict the total number of arcs to the interval $[𝙻𝙾𝚆, 𝚄𝙿]$ .

Parts (A) and (B) of Figure 5.26.1 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐍𝐀𝐑𝐂$ graph property, the arcs of the final graph are stressed in bold.

Figure 5.26.1. Initial and final graph of the $𝚊𝚖𝚘𝚗𝚐_𝚕𝚘𝚠_𝚞𝚙$ constraint


(a)	(b)

Automaton: Figure 5.26.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}$ . The automaton counts the number of variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection that take their value in $𝚅𝙰𝙻𝚄𝙴𝚂$ and finally checks that this number is within the interval $[𝙻𝙾𝚆, 𝚄𝙿]$ .

Figure 5.26.2. Automaton of the $𝚊𝚖𝚘𝚗𝚐_𝚕𝚘𝚠_𝚞𝚙$ constraint

Figure 5.26.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.26. among_low_up

Figure 5.26.1. Initial and final graph of the $𝚊𝚖𝚘𝚗𝚐_𝚕𝚘𝚠_𝚞𝚙$ constraint

Figure 5.26.2. Automaton of the $𝚊𝚖𝚘𝚗𝚐_𝚕𝚘𝚠_𝚞𝚙$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.26. among_low_up

Figure 5.26.1. Initial and final graph of the 𝚊𝚖𝚘𝚗𝚐_𝚕𝚘𝚠_𝚞𝚙 constraint

Figure 5.26.2. Automaton of the 𝚊𝚖𝚘𝚗𝚐_𝚕𝚘𝚠_𝚞𝚙 constraint

Figure 5.26.1. Initial and final graph of the $𝚊𝚖𝚘𝚗𝚐_𝚕𝚘𝚠_𝚞𝚙$ constraint

Figure 5.26.2. Automaton of the $𝚊𝚖𝚘𝚗𝚐_𝚕𝚘𝚠_𝚞𝚙$ constraint