Global Constraint Catalog: Cnext_greater

5.276. next_greater_element

DESCRIPTION

LINKS

GRAPH

Origin

M. Carlsson

Constraint

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

Arguments

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

Restrictions

𝚅𝙰𝚁 1 < 𝚅𝙰𝚁 2

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

Purpose

$𝚅𝙰𝚁 2$ is the value strictly greater than $𝚅𝙰𝚁 1$ located at the smallest possible entry of the table $𝚃𝙰𝙱𝙻𝙴$ . In addition, the variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are sorted in strictly increasing order.

Example

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

The $𝚗𝚎𝚡𝚝_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint holds since:

$𝚅𝙰𝚁 2$ is fixed to the first value 8 strictly greater than $𝚅𝙰𝚁 1 = 7$ ,
The $𝚟𝚊𝚛$ attributes of the items of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are sorted in strictly increasing order.

Typical

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

𝚛𝚊𝚗𝚐𝚎

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

Usage

Originally introduced in [CarlssonBeldiceanu04] for modelling the fact that a nucleotide has to be consumed as soon as possible at cycle $𝚅𝙰𝚁 2$ after a given cycle $𝚅𝙰𝚁 1$ .

Remark

Similar to the $𝚖𝚒𝚗𝚒𝚖𝚞𝚖_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚝𝚑𝚊𝚗$ constraint, except for the fact that the $𝚟𝚊𝚛$ attributes are sorted.

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:

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

implies: $𝚖𝚒𝚗𝚒𝚖𝚞𝚖_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚝𝚑𝚊𝚗$ .

related: $𝚗𝚎𝚡𝚝_𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ (allow to iterate over the values of a table).

Keywords

characteristic of a constraint: minimum, derived collection.

constraint type: order constraint, data constraint.

modelling: table.

Derived Collection

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

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝑃𝐴𝑇𝐻

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

Arc arity

Arc constraint(s)

𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛 < 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛

Graph property(ies)

𝐍𝐀𝐑𝐂

= | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | - 1

Arc input(s)

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

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

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

Graph property(ies)

𝐍𝐀𝐑𝐂

> 0

Sets

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

Constraint(s) on sets

𝚖𝚒𝚗𝚒𝚖𝚞𝚖

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

Graph model

Parts (A) and (B) of Figure 5.276.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 arcs of the final graph are stressed in bold.

Figure 5.276.1. Initial and final graph of the $𝚗𝚎𝚡𝚝_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint


(a)	(b)

Signature

Since the first graph constraint uses the $𝑃𝐴𝑇𝐻$ arc generator on the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection, the number of arcs of the corresponding initial graph is equal to $| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | - 1$ . Therefore the maximum number of arcs of the final graph is equal to $| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | - 1$ . For this reason we can rewrite $𝐍𝐀𝐑𝐂 = | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | - 1$ to $𝐍𝐀𝐑𝐂 \geq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | - 1$ and simplify $\underset{̲}{\bar{𝐍𝐀𝐑𝐂}}$ to $\bar{𝐍𝐀𝐑𝐂}$ .

Global Constraint Catalog

5. Global Constraint Catalogue

5.276. next_greater_element

Figure 5.276.1. Initial and final graph of the 𝚗𝚎𝚡𝚝_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚎𝚕𝚎𝚖𝚎𝚗𝚝 constraint

Figure 5.276.1. Initial and final graph of the $𝚗𝚎𝚡𝚝_𝚐𝚛𝚎𝚊𝚝𝚎𝚛_𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint