Global Constraint Catalog: Cbetween_min

5.40. between_min_max

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Used for defining $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎_𝚌𝚘𝚗𝚟𝚎𝚡$ .

Constraint

$𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡 (𝚅𝙰𝚁, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Arguments

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

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

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

Purpose

$𝚅𝙰𝚁$ is greater than or equal to at least one variable of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ and less than or equal to at least one variable of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Example

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

The $𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ constraint holds since its first argument 3 is greater than or equal to the minimum value of the values of the collection $〈 1, 1, 4, 8 〉$ and less than or equal to the maximum value of $〈 1, 1, 4, 8 〉$ .

Typical

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

𝚛𝚊𝚗𝚐𝚎

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

Symmetries

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are permutable.
$𝚅𝙰𝚁$ can be set to any value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ .

Reformulation

By introducing two extra variables $𝙼𝙸𝙽$ and $𝙼𝙰𝚇$ , the $𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ $(𝚅𝙰𝚁, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ constraint can be expressed in term of the following conjunction of constraints:

$𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ $(𝙼𝙸𝙽, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ ,

$𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ $(𝙼𝙰𝚇, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ ,

$𝚅𝙰𝚁 \geq 𝙼𝙸𝙽$ ,

$𝚅𝙰𝚁 \leq 𝙼𝙰𝚇$ .

Used in

$𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎_𝚌𝚘𝚗𝚟𝚎𝚡$ .

See also

implied by: $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ , $𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ .

Keywords

characteristic of a constraint: automaton, automaton without counters, reified automaton constraint.

constraint network structure: centered cyclic(1) constraint network(1).

Derived Collection

𝚌𝚘𝚕 (𝙸𝚃𝙴𝙼 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛), [𝚒𝚝𝚎𝚖 (𝚟𝚊𝚛 - 𝚅𝙰𝚁)])

Arc input(s)

$𝙸𝚃𝙴𝙼$ $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

𝚒𝚝𝚎𝚖 . 𝚟𝚊𝚛 \geq 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚟𝚊𝚛

Graph property(ies)

𝐍𝐀𝐑𝐂

\geq 1

Graph class

•

𝙰𝙲𝚈𝙲𝙻𝙸𝙲

•

𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴

•

𝙽𝙾_𝙻𝙾𝙾𝙿

Arc input(s)

$𝙸𝚃𝙴𝙼$ $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

𝚒𝚝𝚎𝚖 . 𝚟𝚊𝚛 \leq 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚟𝚊𝚛

Graph property(ies)

𝐍𝐀𝐑𝐂

\geq 1

Graph class

•

𝙰𝙲𝚈𝙲𝙻𝙸𝙲

•

𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴

•

𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

Parts (A) and (B) of Figure 5.40.1 respectively show the initial and final graph associated with the second graph constraint of the Example slot. Since we use the $𝐍𝐀𝐑𝐂$ graph property, the two arcs of the final graph are stressed in bold. The constraint holds since 3 is greater than 1 and since 3 is less than 8.

Figure 5.40.1. Initial and final graph of the $𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ constraint


(a)	(b)

Automaton: Figure 5.40.2 depicts the automaton associated with the $𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ constraint. To each pair $(𝚅𝙰𝚁, {𝚅𝙰𝚁}_{i})$ , where ${𝚅𝙰𝚁}_{i}$ is a variable of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ corresponds a signature variable $𝚂_{i}$ . The following signature constraint links $𝚅𝙰𝚁$ , ${𝚅𝙰𝚁}_{i}$ and $𝚂_{i}$ : $(𝚅𝙰𝚁 < {𝚅𝙰𝚁}_{i} \Leftrightarrow 𝚂_{i} = 0) \land (𝚅𝙰𝚁 = {𝚅𝙰𝚁}_{i} \Leftrightarrow 𝚂_{i} = 1) \land (𝚅𝙰𝚁 > {𝚅𝙰𝚁}_{i} \Leftrightarrow 𝚂_{i} = 2)$ .

Figure 5.40.2. Automaton of the $𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ constraint

Figure 5.40.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.40. between_min_max

Figure 5.40.1. Initial and final graph of the $𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ constraint

Figure 5.40.2. Automaton of the $𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ constraint

Figure 5.40.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ constraint

W3C: XHTML - last update: 2010-12-6. SD.

Global Constraint Catalog

5. Global Constraint Catalogue

5.40. between_min_max

Figure 5.40.1. Initial and final graph of the 𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡 constraint

Figure 5.40.2. Automaton of the 𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡 constraint

Figure 5.40.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡 constraint

W3C: XHTML - last update: 2010-12-6. SD.

Figure 5.40.1. Initial and final graph of the $𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ constraint

Figure 5.40.2. Automaton of the $𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ constraint

Figure 5.40.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ constraint