Global Constraint Catalog: Cbetween_min

5.50. 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〉)

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

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

The first $𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ 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 $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ .

Arg. properties

Extensible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Reformulation

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

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

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

$𝚅𝙰𝚁 \geq 𝙼𝙸𝙽$ ,

$𝚅𝙰𝚁 \leq 𝙼𝙰𝚇$ .

Counting

Length ( $n$ )	2	3	4	5	6	7	8
Solutions	17	184	2417	37806	689201	14376608	338051265

Number of solutions for $𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ : domains $0 . . n$

ctrs/between_min_max-1-tikz

ctrs/between_min_max-2-tikz

Length (

n

)

Total

184

2417

37806

689201

14376608

338051265

Parameter

value

369

4651

70993

1273609

26269505

543

6751

102023

1817215

37281919

593

7501

113489

2018899

41366849

543

7501

116191

2078581

42649535

369

6751

113489

2078581

42915649

4651

102023

2018899

42649535

70993

1817215

41366849

1273609

37281919

26269505

Solution count for $𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ : domains $0 . . n$

ctrs/between_min_max-3-tikz

ctrs/between_min_max-4-tikz

Used in

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

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.50.1 respectively show the initial and final graph associated with the second graph constraint of the first example 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.50.1. Initial and final graph of the $𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ constraint


(a)	(b)

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

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

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

Global Constraint Catalog

5. Global Constraint Catalogue

5.50. between_min_max

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

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

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

Global Constraint Catalog

5. Global Constraint Catalogue

5.50. between_min_max

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

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

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

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

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

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