Global Constraint Catalog: Celement

5.140. element_greatereq

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

[OttossonThorsteinssonHooker99]

Constraint

$𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚 (𝙸𝚃𝙴𝙼, 𝚃𝙰𝙱𝙻𝙴)$

Arguments

$𝙸𝚃𝙴𝙼$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚗𝚍𝚎𝚡 - 𝚍𝚟𝚊𝚛, 𝚟𝚊𝚕𝚞𝚎 - 𝚍𝚟𝚊𝚛)$
$𝚃𝙰𝙱𝙻𝙴$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚗𝚍𝚎𝚡 - 𝚒𝚗𝚝, 𝚟𝚊𝚕𝚞𝚎 - 𝚒𝚗𝚝)$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙸𝚃𝙴𝙼, [𝚒𝚗𝚍𝚎𝚡, 𝚟𝚊𝚕𝚞𝚎])

𝙸𝚃𝙴𝙼 . 𝚒𝚗𝚍𝚎𝚡 \geq 1

𝙸𝚃𝙴𝙼 . 𝚒𝚗𝚍𝚎𝚡 \leq | 𝚃𝙰𝙱𝙻𝙴 |

| 𝙸𝚃𝙴𝙼 | = 1

| 𝚃𝙰𝙱𝙻𝙴 | > 0

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚃𝙰𝙱𝙻𝙴, [𝚒𝚗𝚍𝚎𝚡, 𝚟𝚊𝚕𝚞𝚎])

𝚃𝙰𝙱𝙻𝙴 . 𝚒𝚗𝚍𝚎𝚡 \geq 1

𝚃𝙰𝙱𝙻𝙴 . 𝚒𝚗𝚍𝚎𝚡 \leq | 𝚃𝙰𝙱𝙻𝙴 |

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

(𝚃𝙰𝙱𝙻𝙴, 𝚒𝚗𝚍𝚎𝚡)

Purpose

$𝙸𝚃𝙴𝙼 [1] . 𝚟𝚊𝚕𝚞𝚎$ is greater than or equal to one of the entries (i.e., the $𝚟𝚊𝚕𝚞𝚎$ attribute) of the table $𝚃𝙰𝙱𝙻𝙴$ .

Example

(\begin{matrix} 〈𝚒𝚗𝚍𝚎𝚡 - 1 𝚟𝚊𝚕𝚞𝚎 - 8〉, \\ 〈\begin{matrix} 𝚒𝚗𝚍𝚎𝚡 - 1 & 𝚟𝚊𝚕𝚞𝚎 - 6, \\ 𝚒𝚗𝚍𝚎𝚡 - 2 & 𝚟𝚊𝚕𝚞𝚎 - 9, \\ 𝚒𝚗𝚍𝚎𝚡 - 3 & 𝚟𝚊𝚕𝚞𝚎 - 2, \\ 𝚒𝚗𝚍𝚎𝚡 - 4 & 𝚟𝚊𝚕𝚞𝚎 - 9 \end{matrix}〉 \end{matrix})

The $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚$ constraint holds since $𝙸𝚃𝙴𝙼 [1] . 𝚟𝚊𝚕𝚞𝚎 = 8$ is greater than or equal to $𝚃𝙰𝙱𝙻𝙴 [𝙸𝚃𝙴𝙼 [1] . 𝚒𝚗𝚍𝚎𝚡] . 𝚟𝚊𝚕𝚞𝚎 = 𝚃𝙰𝙱𝙻𝙴 [1] . 𝚟𝚊𝚕𝚞𝚎 = 6$ .

Typical

| 𝚃𝙰𝙱𝙻𝙴 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚃𝙰𝙱𝙻𝙴 . 𝚟𝚊𝚕𝚞𝚎) > 1

Symmetries

Items of $𝚃𝙰𝙱𝙻𝙴$ are permutable.
All occurrences of two distinct values in $𝙸𝚃𝙴𝙼 . 𝚟𝚊𝚕𝚞𝚎$ or $𝚃𝙰𝙱𝙻𝙴 . 𝚟𝚊𝚕𝚞𝚎$ can be swapped; all occurrences of a value in $𝙸𝚃𝙴𝙼 . 𝚟𝚊𝚕𝚞𝚎$ or $𝚃𝙰𝙱𝙻𝙴 . 𝚟𝚊𝚕𝚞𝚎$ can be renamed to any unused value.

Usage

Used for modelling variable subscripts in linear constraints [OttossonThorsteinssonHooker99].

Reformulation

By introducing an extra variable $𝚅𝙰𝙻$ , the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚$ $(〈 𝚒𝚗𝚍𝚎𝚡 - 𝙸𝙽𝙳𝙴𝚇 𝚟𝚊𝚕𝚞𝚎 - 𝚅𝙰𝙻𝚄𝙴 〉, 𝚃𝙰𝙱𝙻𝙴)$ constraint can be expressed in term of an $𝚎𝚕𝚎𝚖$ $(〈 𝚒𝚗𝚍𝚎𝚡 - 𝙸𝙽𝙳𝙴𝚇 𝚟𝚊𝚕𝚞𝚎 - 𝚅𝙰𝙻 〉, 𝚃𝙰𝙱𝙻𝙴)$ constraint and of an inequality constraint $𝚅𝙰𝙻𝚄𝙴 \geq 𝚅𝙰𝙻$ .

implied by: $𝚎𝚕𝚎𝚖$ .

Keywords

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

constraint arguments: binary constraint.

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

constraint type: data constraint.

filtering: linear programming, arc-consistency.

modelling: array constraint, table, variable subscript, variable indexing.

Arc input(s)

$𝙸𝚃𝙴𝙼$ $𝚃𝙰𝙱𝙻𝙴$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

• 𝚒𝚝𝚎𝚖 . 𝚒𝚗𝚍𝚎𝚡 = 𝚝𝚊𝚋𝚕𝚎 . 𝚒𝚗𝚍𝚎𝚡

• 𝚒𝚝𝚎𝚖 . 𝚟𝚊𝚕𝚞𝚎 \geq 𝚝𝚊𝚋𝚕𝚎 . 𝚟𝚊𝚕𝚞𝚎

Graph property(ies)

𝐍𝐀𝐑𝐂

= 1

Graph model

Similar to the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint except that the equality constraint of the second condition of the arc constraint is replaced by a greater than or equal to constraint.

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

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


(a)	(b)

Signature

Since all the $𝚒𝚗𝚍𝚎𝚡$ attributes of $𝚃𝙰𝙱𝙻𝙴$ are distinct and because of the first arc constraint the final graph cannot have more than one arc. Therefore we can rewrite $𝐍𝐀𝐑𝐂 = 1$ to $𝐍𝐀𝐑𝐂 \geq 1$ and simplify $\underset{̲}{\bar{𝐍𝐀𝐑𝐂}}$ to $\bar{𝐍𝐀𝐑𝐂}$ .

Automaton: Figure 5.140.2 depicts the automaton associated with the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚$ constraint. Let $𝙸𝙽𝙳𝙴𝚇$ and $𝚅𝙰𝙻𝚄𝙴$ respectively be the $𝚒𝚗𝚍𝚎𝚡$ and the $𝚟𝚊𝚕𝚞𝚎$ attributes of the unique item of the $𝙸𝚃𝙴𝙼$ collection. Let ${𝙸𝙽𝙳𝙴𝚇}_{i}$ and ${𝚅𝙰𝙻𝚄𝙴}_{i}$ respectively be the $𝚒𝚗𝚍𝚎𝚡$ and the $𝚟𝚊𝚕𝚞𝚎$ attributes of the $i^{t h}$ item of the $𝚃𝙰𝙱𝙻𝙴$ collection. To each quadruple $(𝙸𝙽𝙳𝙴𝚇, 𝚅𝙰𝙻𝚄𝙴, {𝙸𝙽𝙳𝙴𝚇}_{i}, {𝚅𝙰𝙻𝚄𝙴}_{i})$ corresponds a 0-1 signature variable $S_{i}$ as well as the following signature constraint: $((𝙸𝙽𝙳𝙴𝚇 = {𝙸𝙽𝙳𝙴𝚇}_{i}) \land (𝚅𝙰𝙻𝚄𝙴 \geq {𝚅𝙰𝙻𝚄𝙴}_{i})) \Leftrightarrow S_{i}$ .

Figure 5.140.2. Automaton of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚$ constraint

Figure 5.140.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.140. element_greatereq

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

Figure 5.140.2. Automaton of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚$ constraint

Figure 5.140.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.140. element_greatereq

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

Figure 5.140.2. Automaton of the 𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚 constraint

Figure 5.140.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚 constraint

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

Figure 5.140.2. Automaton of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚$ constraint

Figure 5.140.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚$ constraint