Global Constraint Catalog: Cminimum_greater

5.264. minimum_greater_than

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

N. Beldiceanu

Constraint

$𝚖𝚒𝚗𝚒𝚖𝚞𝚖_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚝𝚑𝚊𝚗 (𝚅𝙰𝚁 1, 𝚅𝙰𝚁 2, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Arguments

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

Restrictions

𝚅𝙰𝚁 1 > 𝚅𝙰𝚁 2

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

Purpose

$𝚅𝙰𝚁 1$ is the smallest value strictly greater than $𝚅𝙰𝚁 2$ of the collection of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ : this concretely means that there exists at least one variable of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ that takes a value strictly greater than $𝚅𝙰𝚁 2$ .

Example

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

The $𝚖𝚒𝚗𝚒𝚖𝚞𝚖_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚝𝚑𝚊𝚗$ constraint holds since value 5 is the smallest value strictly greater than value 3 among values $8, 5, 3$ and 8.

Typical

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

𝚛𝚊𝚗𝚐𝚎

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

Symmetry

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are permutable.

Arg. properties

Aggregate: $𝚅𝙰𝚁 1 (𝚖𝚒𝚗)$ , $𝚅𝙰𝚁 2 (𝚒𝚍)$ , $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 (𝚞𝚗𝚒𝚘𝚗)$ .

Reformulation

Let $V_{1}, V_{2}, \dots, V_{| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |}$ denote the variables of the collection of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ . By creating the extra variables $M$ and $U_{1}, U_{2}, \dots, U_{| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |}$ , the $𝚖𝚒𝚗𝚒𝚖𝚞𝚖_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚝𝚑𝚊𝚗$ constraint can be expressed in term of the following constraints:

$𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ $(M, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ ,
$𝚅𝙰𝚁 1 > 𝚅𝙰𝚁 2$ ,
$𝚅𝙰𝚁 1 \leq M$ ,
$V_{i} \leq 𝚅𝙰𝚁 2 \Rightarrow U_{i} = M (i \in [1, | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |])$ ,
$V_{i} > 𝚅𝙰𝚁 2 \Rightarrow U_{i} = V_{i} (i \in [1, | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |])$ ,
$𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ $(𝚅𝙰𝚁 1, 〈 U_{1}, U_{2}, \dots, U_{| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |} 〉)$ .

implied by: $𝚗𝚎𝚡𝚝_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ .

related: $𝚗𝚎𝚡𝚝_𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ (identify an element in a table).

Keywords

characteristic of a constraint: minimum, automaton, automaton without counters, reified automaton constraint, derived collection.

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

constraint type: order constraint.

Derived Collection

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

Arc input(s)

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

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

𝚒𝚝𝚎𝚖 . 𝚟𝚊𝚛 < 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚟𝚊𝚛

Graph property(ies)

𝐍𝐀𝐑𝐂

> 0

Sets

𝖲𝖴𝖢𝖢 \mapsto [𝚜𝚘𝚞𝚛𝚌𝚎, 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜]

Constraint(s) on sets

𝚖𝚒𝚗𝚒𝚖𝚞𝚖

(𝚅𝙰𝚁 1, 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜)

Graph model

Similar to the $𝚗𝚎𝚡𝚝_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint, except that there is no order on the variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Parts (A) and (B) of Figure 5.264.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. The source and the sinks of the final graph respectively correspond to the variable $𝚅𝙰𝚁 2$ and to the variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection that are strictly greater than $𝚅𝙰𝚁 2$ . $𝚅𝙰𝚁 1$ is set to the smallest value of the $𝚟𝚊𝚛$ attribute of the sinks of the final graph.

Figure 5.264.1. Initial and final graph of the $𝚖𝚒𝚗𝚒𝚖𝚞𝚖_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚝𝚑𝚊𝚗$ constraint


(a)	(b)

Automaton

Figure 5.264.2 depicts the automaton associated with the $𝚖𝚒𝚗𝚒𝚖𝚞𝚖_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚝𝚑𝚊𝚗$ constraint. Let ${𝚅𝙰𝚁}_{i}$ be the $i^{t h}$ variable of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection. To each triple $(𝚅𝙰𝚁 1, 𝚅𝙰𝚁 2, {𝚅𝙰𝚁}_{i})$ corresponds a signature variable $S_{i}$ as well as the following signature constraint:

$(({𝚅𝙰𝚁}_{i} < 𝚅𝙰𝚁 1) \land ({𝚅𝙰𝚁}_{i} \leq 𝚅𝙰𝚁 2)) \Leftrightarrow S_{i} = 0 \land$

$(({𝚅𝙰𝚁}_{i} = 𝚅𝙰𝚁 1) \land ({𝚅𝙰𝚁}_{i} \leq 𝚅𝙰𝚁 2)) \Leftrightarrow S_{i} = 1 \land$

$(({𝚅𝙰𝚁}_{i} > 𝚅𝙰𝚁 1) \land ({𝚅𝙰𝚁}_{i} \leq 𝚅𝙰𝚁 2)) \Leftrightarrow S_{i} = 2 \land$

$(({𝚅𝙰𝚁}_{i} < 𝚅𝙰𝚁 1) \land ({𝚅𝙰𝚁}_{i} > 𝚅𝙰𝚁 2)) \Leftrightarrow S_{i} = 3 \land$

$(({𝚅𝙰𝚁}_{i} = 𝚅𝙰𝚁 1) \land ({𝚅𝙰𝚁}_{i} > 𝚅𝙰𝚁 2)) \Leftrightarrow S_{i} = 4 \land$

$(({𝚅𝙰𝚁}_{i} > 𝚅𝙰𝚁 1) \land ({𝚅𝙰𝚁}_{i} > 𝚅𝙰𝚁 2)) \Leftrightarrow S_{i} = 5$ .

The automaton is constructed in order to fulfil the following conditions:

We look for an item of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection such that ${𝚟𝚊𝚛}_{i} = 𝚅𝙰𝚁 1$ and ${𝚟𝚊𝚛}_{i} > 𝚅𝙰𝚁 2$ ,
There should not exist any item of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection such that ${𝚟𝚊𝚛}_{i} < 𝚅𝙰𝚁 1$ and ${𝚟𝚊𝚛}_{i} > 𝚅𝙰𝚁 2$ .

Figure 5.264.2. Automaton of the $𝚖𝚒𝚗𝚒𝚖𝚞𝚖_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚝𝚑𝚊𝚗$ constraint

Figure 5.264.3. Hypergraph of the reformulation corresponding to the counter free non deterministic automaton of the $𝚖𝚒𝚗𝚒𝚖𝚞𝚖_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚝𝚑𝚊𝚗$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.264. minimum_greater_than

Figure 5.264.1. Initial and final graph of the 𝚖𝚒𝚗𝚒𝚖𝚞𝚖_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚝𝚑𝚊𝚗 constraint

Figure 5.264.2. Automaton of the 𝚖𝚒𝚗𝚒𝚖𝚞𝚖_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚝𝚑𝚊𝚗 constraint

Figure 5.264.3. Hypergraph of the reformulation corresponding to the counter free non deterministic automaton of the 𝚖𝚒𝚗𝚒𝚖𝚞𝚖_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚝𝚑𝚊𝚗 constraint

Figure 5.264.1. Initial and final graph of the $𝚖𝚒𝚗𝚒𝚖𝚞𝚖_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚝𝚑𝚊𝚗$ constraint

Figure 5.264.2. Automaton of the $𝚖𝚒𝚗𝚒𝚖𝚞𝚖_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚝𝚑𝚊𝚗$ constraint

Figure 5.264.3. Hypergraph of the reformulation corresponding to the counter free non deterministic automaton of the $𝚖𝚒𝚗𝚒𝚖𝚞𝚖_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚝𝚑𝚊𝚗$ constraint