Global Constraint Catalog: Ccond_lex

5.82. cond_lex_greatereq

DESCRIPTION

LINKS

AUTOMATON

Origin

Inspired by [WallaceWilson06].

Constraint

$𝚌𝚘𝚗𝚍_𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚 (𝚅𝙴𝙲𝚃𝙾𝚁 1, 𝚅𝙴𝙲𝚃𝙾𝚁 2, 𝙿𝚁𝙴𝙵𝙴𝚁𝙴𝙽𝙲𝙴_𝚃𝙰𝙱𝙻𝙴)$

Type

𝚃𝚄𝙿𝙻𝙴_𝙾𝙵_𝚅𝙰𝙻𝚂

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚕 - 𝚒𝚗𝚝)

Arguments

$𝚅𝙴𝙲𝚃𝙾𝚁 1$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝚅𝙴𝙲𝚃𝙾𝚁 2$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝙿𝚁𝙴𝙵𝙴𝚁𝙴𝙽𝙲𝙴_𝚃𝙰𝙱𝙻𝙴$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚝𝚞𝚙𝚕𝚎 - 𝚃𝚄𝙿𝙻𝙴_𝙾𝙵_𝚅𝙰𝙻𝚂)$

Restrictions

| 𝚃𝚄𝙿𝙻𝙴_𝙾𝙵_𝚅𝙰𝙻𝚂 | \geq 1

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚃𝚄𝙿𝙻𝙴_𝙾𝙵_𝚅𝙰𝙻𝚂, 𝚟𝚊𝚕)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙴𝙲𝚃𝙾𝚁 1, 𝚟𝚊𝚛)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙴𝙲𝚃𝙾𝚁 2, 𝚟𝚊𝚛)

| 𝚅𝙴𝙲𝚃𝙾𝚁 1 | = | 𝚅𝙴𝙲𝚃𝙾𝚁 2 |

| 𝚅𝙴𝙲𝚃𝙾𝚁 1 | = | 𝚃𝚄𝙿𝙻𝙴_𝙾𝙵_𝚅𝙰𝙻𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙿𝚁𝙴𝙵𝙴𝚁𝙴𝙽𝙲𝙴_𝚃𝙰𝙱𝙻𝙴, 𝚝𝚞𝚙𝚕𝚎)

𝚜𝚊𝚖𝚎_𝚜𝚒𝚣𝚎

(𝙿𝚁𝙴𝙵𝙴𝚁𝙴𝙽𝙲𝙴_𝚃𝙰𝙱𝙻𝙴, 𝚝𝚞𝚙𝚕𝚎)

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

(𝙿𝚁𝙴𝙵𝙴𝚁𝙴𝙽𝙲𝙴_𝚃𝙰𝙱𝙻𝙴, [])

𝚒𝚗_𝚛𝚎𝚕𝚊𝚝𝚒𝚘𝚗

(𝚅𝙴𝙲𝚃𝙾𝚁 1, 𝙿𝚁𝙴𝙵𝙴𝚁𝙴𝙽𝙲𝙴_𝚃𝙰𝙱𝙻𝙴)

𝚒𝚗_𝚛𝚎𝚕𝚊𝚝𝚒𝚘𝚗

(𝚅𝙴𝙲𝚃𝙾𝚁 2, 𝙿𝚁𝙴𝙵𝙴𝚁𝙴𝙽𝙲𝙴_𝚃𝙰𝙱𝙻𝙴)

Purpose

$𝚅𝙴𝙲𝚃𝙾𝚁 1$ and $𝚅𝙴𝙲𝚃𝙾𝚁 2$ are both assigned to the $𝙸^{t h}$ and $𝙹^{t h}$ items of the collection $𝙿𝚁𝙴𝙵𝙴𝚁𝙴𝙽𝙲𝙴_𝚃𝙰𝙱𝙻𝙴$ such that $𝙸 \geq 𝙹$ .

Example

(\begin{matrix} 〈0, 0〉, \\ 〈1, 0〉, \\ 〈\begin{matrix} 𝚝𝚞𝚙𝚕𝚎 - 〈1, 0〉, \\ 𝚝𝚞𝚙𝚕𝚎 - 〈0, 1〉, \\ 𝚝𝚞𝚙𝚕𝚎 - 〈0, 0〉, \\ 𝚝𝚞𝚙𝚕𝚎 - 〈1, 1〉 \end{matrix}〉 \end{matrix})

The $𝚌𝚘𝚗𝚍_𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚$ constraint holds since $𝚅𝙴𝙲𝚃𝙾𝚁 1$ and $𝚅𝙴𝙲𝚃𝙾𝚁 2$ are respectively assigned to the third and first items of the collection $𝙿𝚁𝙴𝙵𝙴𝚁𝙴𝙽𝙲𝙴_𝚃𝙰𝙱𝙻𝙴$ .

Typical

| 𝚃𝚄𝙿𝙻𝙴_𝙾𝙵_𝚅𝙰𝙻𝚂 | > 1

| 𝚅𝙴𝙲𝚃𝙾𝚁 1 | > 1

| 𝚅𝙴𝙲𝚃𝙾𝚁 2 | > 1

| 𝙿𝚁𝙴𝙵𝙴𝚁𝙴𝙽𝙲𝙴_𝚃𝙰𝙱𝙻𝙴 | > 1

Symmetries

Items of $𝚅𝙴𝙲𝚃𝙾𝚁 1$ , $𝚅𝙴𝙲𝚃𝙾𝚁 2$ and $𝙿𝚁𝙴𝙵𝙴𝚁𝙴𝙽𝙲𝙴_𝚃𝙰𝙱𝙻𝙴 . 𝚝𝚞𝚙𝚕𝚎$ are permutable (same permutation used).
All occurrences of two distinct tuples of values in $𝚅𝙴𝙲𝚃𝙾𝚁 1$ , $𝚅𝙴𝙲𝚃𝙾𝚁 2$ or $𝙿𝚁𝙴𝙵𝙴𝚁𝙴𝙽𝙲𝙴_𝚃𝙰𝙱𝙻𝙴 . 𝚝𝚞𝚙𝚕𝚎$ can be swapped; all occurrences of a tuple of values in $𝚅𝙴𝙲𝚃𝙾𝚁 1$ , $𝚅𝙴𝙲𝚃𝙾𝚁 2$ or $𝙿𝚁𝙴𝙵𝙴𝚁𝙴𝙽𝙲𝙴_𝚃𝙰𝙱𝙻𝙴 . 𝚝𝚞𝚙𝚕𝚎$ can be renamed to any unused tuple of values.

Usage

See $𝚌𝚘𝚗𝚍_𝚕𝚎𝚡_𝚌𝚘𝚜𝚝$ .

implied by: $𝚌𝚘𝚗𝚍_𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛$ .

Keywords

characteristic of a constraint: vector, automaton.

constraint network structure: Berge-acyclic constraint network.

constraint type: order constraint.

filtering: arc-consistency.

modelling: preferences.

symmetry: lexicographic order.

Automaton

Figure 5.82.1 depicts the automaton associated with the preference table of the $𝚌𝚘𝚗𝚍_𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚$ constraint given in the example. Let $𝚅𝙰𝚁 1_{k}$ and $𝚅𝙰𝚁 2_{k}$ respectively be the $𝚟𝚊𝚛$ attributes of the $k^{t h}$ items of the $𝚅𝙴𝙲𝚃𝙾𝚁 1$ and the $𝚅𝙴𝙲𝚃𝙾𝚁 2$ collections. Figure 5.82.2 depicts the reformulation of the $𝚌𝚘𝚗𝚍_𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚$ constraint. This reformulation uses:

Two occurrences of the automaton depicted by Figure 5.82.1 for computing the positions $𝙸$ and $𝙹$ within the preference table corresponding to $𝚅𝙴𝙲𝚃𝙾𝚁 1$ and $𝚅𝙴𝙲𝚃𝙾𝚁 2$ .
The binary constraint $𝙸 \geq 𝙹$ .

Figure 5.82.1. Automaton associated with the preference table of the $𝚌𝚘𝚗𝚍_𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚$ constraint given in the Example slot

Figure 5.82.2. Hypergraph of the reformulation corresponding to the $𝚌𝚘𝚗𝚍_𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚$ constraint: it uses two occurrences of the automaton of Figure 5.82.1 and the constraint $𝙸 \geq 𝙹$

Global Constraint Catalog

5. Global Constraint Catalogue

5.82. cond_lex_greatereq

Figure 5.82.1. Automaton associated with the preference table of the 𝚌𝚘𝚗𝚍_𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚 constraint given in the Example slot

Figure 5.82.2. Hypergraph of the reformulation corresponding to the 𝚌𝚘𝚗𝚍_𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚 constraint: it uses two occurrences of the automaton of Figure 5.82.1 and the constraint 𝙸≥𝙹

Figure 5.82.1. Automaton associated with the preference table of the $𝚌𝚘𝚗𝚍_𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚$ constraint given in the Example slot

Figure 5.82.2. Hypergraph of the reformulation corresponding to the $𝚌𝚘𝚗𝚍_𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚$ constraint: it uses two occurrences of the automaton of Figure 5.82.1 and the constraint $𝙸 \geq 𝙹$