Global Constraint Catalog: Clex

5.222. lex_between

DESCRIPTION

LINKS

AUTOMATON

Origin

[BeldiceanuCarlsson02c]

Constraint

$𝚕𝚎𝚡_𝚋𝚎𝚝𝚠𝚎𝚎𝚗 (𝙻𝙾𝚆𝙴𝚁_𝙱𝙾𝚄𝙽𝙳, 𝚅𝙴𝙲𝚃𝙾𝚁, 𝚄𝙿𝙿𝙴𝚁_𝙱𝙾𝚄𝙽𝙳)$

Synonym

$𝚋𝚎𝚝𝚠𝚎𝚎𝚗$ .

Arguments

$𝙻𝙾𝚆𝙴𝚁_𝙱𝙾𝚄𝙽𝙳$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚒𝚗𝚝)$
$𝚅𝙴𝙲𝚃𝙾𝚁$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝚄𝙿𝙿𝙴𝚁_𝙱𝙾𝚄𝙽𝙳$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚒𝚗𝚝)$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙻𝙾𝚆𝙴𝚁_𝙱𝙾𝚄𝙽𝙳, 𝚟𝚊𝚛)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚄𝙿𝙿𝙴𝚁_𝙱𝙾𝚄𝙽𝙳, 𝚟𝚊𝚛)

| 𝙻𝙾𝚆𝙴𝚁_𝙱𝙾𝚄𝙽𝙳 | = | 𝚅𝙴𝙲𝚃𝙾𝚁 |

| 𝚄𝙿𝙿𝙴𝚁_𝙱𝙾𝚄𝙽𝙳 | = | 𝚅𝙴𝙲𝚃𝙾𝚁 |

𝚕𝚎𝚡_𝚕𝚎𝚜𝚜𝚎𝚚

(𝙻𝙾𝚆𝙴𝚁_𝙱𝙾𝚄𝙽𝙳, 𝚅𝙴𝙲𝚃𝙾𝚁)

𝚕𝚎𝚡_𝚕𝚎𝚜𝚜𝚎𝚚

(𝚅𝙴𝙲𝚃𝙾𝚁, 𝚄𝙿𝙿𝙴𝚁_𝙱𝙾𝚄𝙽𝙳)

Purpose

The vector $𝚅𝙴𝙲𝚃𝙾𝚁$ is lexicographically greater than or equal to the fixed vector $𝙻𝙾𝚆𝙴𝚁_𝙱𝙾𝚄𝙽𝙳$ and lexicographically smaller than or equal to the fixed vector $𝚄𝙿𝙿𝙴𝚁_𝙱𝙾𝚄𝙽𝙳$ .

Example

(〈5, 2, 3, 9〉, 〈5, 2, 6, 2〉, 〈5, 2, 6, 3〉)

The $𝚕𝚎𝚡_𝚋𝚎𝚝𝚠𝚎𝚎𝚗$ constraint holds since:

The vector $𝚅𝙴𝙲𝚃𝙾𝚁 = 〈 5, 2, 6, 2 〉$ is greater than or equal to the vector $𝙻𝙾𝚆𝙴𝚁_𝙱𝙾𝚄𝙽𝙳 = 〈 5, 2, 3, 9 〉$ .
The vector $𝚅𝙴𝙲𝚃𝙾𝚁 = 〈 5, 2, 6, 2 〉$ is less than or equal to the vector $𝚄𝙿𝙿𝙴𝚁_𝙱𝙾𝚄𝙽𝙳 = 〈 5, 2, 6, 3 〉$ .

Typical

| 𝙻𝙾𝚆𝙴𝚁_𝙱𝙾𝚄𝙽𝙳 | > 1

𝚕𝚎𝚡_𝚕𝚎𝚜𝚜𝚎𝚚

(𝙻𝙾𝚆𝙴𝚁_𝙱𝙾𝚄𝙽𝙳, 𝚄𝙿𝙿𝙴𝚁_𝙱𝙾𝚄𝙽𝙳)

Symmetries

$𝙻𝙾𝚆𝙴𝚁_𝙱𝙾𝚄𝙽𝙳 . 𝚟𝚊𝚛$ can be decreased.
$𝚄𝙿𝙿𝙴𝚁_𝙱𝙾𝚄𝙽𝙳 . 𝚟𝚊𝚛$ can be increased.

Arg. properties

Suffix-contractible wrt. $𝙻𝙾𝚆𝙴𝚁_𝙱𝙾𝚄𝙽𝙳$ , $𝚅𝙴𝙲𝚃𝙾𝚁$ and $𝚄𝙿𝙿𝙴𝚁_𝙱𝙾𝚄𝙽𝙳$ (remove items from same position).

Usage

This constraint does usually not occur explicitly in practice. However it shows up indirectly in the context of the $𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜$ and the $𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜𝚎𝚚$ constraints: in order to have a complete filtering algorithm for the $𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜$ and the $𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜𝚎𝚚$ constraints one has to come up with a complete filtering algorithm for the $𝚕𝚎𝚡_𝚋𝚎𝚝𝚠𝚎𝚎𝚗$ constraint. The reason is that the $𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜$ as well as the $𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜𝚎𝚚$ constraints both compute feasible lower and upper bounds for each vector they mention. Therefore one ends up with a $𝚕𝚎𝚡_𝚋𝚎𝚝𝚠𝚎𝚎𝚗$ constraint for each vector of the $𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜$ and $𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜𝚎𝚚$ constraints.

Algorithm

[BeldiceanuCarlsson02c].

Reformulation

The $𝚕𝚎𝚡_𝚋𝚎𝚝𝚠𝚎𝚎𝚗$ $(𝙻𝙾𝚆𝙴𝚁_𝙱𝙾𝚄𝙽𝙳, 𝚅𝙴𝙲𝚃𝙾𝚁𝚂, 𝚄𝙿𝙿𝙴𝚁_𝙱𝙾𝚄𝙽𝙳)$ constraint can be expressed as the conjunction $𝚕𝚎𝚡_𝚕𝚎𝚜𝚜𝚎𝚚$ $(𝙻𝙾𝚆𝙴𝚁_𝙱𝙾𝚄𝙽𝙳, 𝚅𝙴𝙲𝚃𝙾𝚁𝚂) \land$ $𝚕𝚎𝚡_𝚕𝚎𝚜𝚜𝚎𝚚$ $(𝚅𝙴𝙲𝚃𝙾𝚁𝚂, 𝚄𝙿𝙿𝙴𝚁_𝙱𝙾𝚄𝙽𝙳)$ .

Systems

lexChainEq in Choco, lex_chain in SICStus.

part of system of constraints: $𝚕𝚎𝚡_𝚕𝚎𝚜𝚜𝚎𝚚$ .

Keywords

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

constraint network structure: Berge-acyclic constraint network.

constraint type: order constraint, system of constraints.

filtering: arc-consistency.

symmetry: symmetry, lexicographic order.

Automaton

Figure 5.222.1 depicts the automaton associated with the $𝚕𝚎𝚡_𝚋𝚎𝚝𝚠𝚎𝚎𝚗$ constraint. Let $𝙻_{i}$ , $𝚅_{i}$ and $𝚄_{i}$ respectively be the $𝚟𝚊𝚛$ attributes of the $i^{t h}$ items of the $𝙻𝙾𝚆𝙴𝚁_𝙱𝙾𝚄𝙽𝙳$ , the $𝚅𝙴𝙲𝚃𝙾𝚁$ and the $𝚄𝙿𝙿𝙴𝚁_𝙱𝙾𝚄𝙽𝙳$ collections. To each triple $(𝙻_{i}, 𝚅_{i}, 𝚄_{i})$ corresponds a signature variable $S_{i}$ as well as the following signature constraint:

$(𝙻_{i} < 𝚅_{i}) \land (𝚅_{i} < 𝚄_{i}) \Leftrightarrow S_{i} = 0 \land$

$(𝙻_{i} < 𝚅_{i}) \land (𝚅_{i} = 𝚄_{i}) \Leftrightarrow S_{i} = 1 \land$

$(𝙻_{i} < 𝚅_{i}) \land (𝚅_{i} > 𝚄_{i}) \Leftrightarrow S_{i} = 2 \land$

$(𝙻_{i} = 𝚅_{i}) \land (𝚅_{i} < 𝚄_{i}) \Leftrightarrow S_{i} = 3 \land$

$(𝙻_{i} = 𝚅_{i}) \land (𝚅_{i} = 𝚄_{i}) \Leftrightarrow S_{i} = 4 \land$

$(𝙻_{i} = 𝚅_{i}) \land (𝚅_{i} > 𝚄_{i}) \Leftrightarrow S_{i} = 5 \land$

$(𝙻_{i} > 𝚅_{i}) \land (𝚅_{i} < 𝚄_{i}) \Leftrightarrow S_{i} = 6 \land$

$(𝙻_{i} > 𝚅_{i}) \land (𝚅_{i} = 𝚄_{i}) \Leftrightarrow S_{i} = 7 \land$

$(𝙻_{i} > 𝚅_{i}) \land (𝚅_{i} > 𝚄_{i}) \Leftrightarrow S_{i} = 8$ .

Figure 5.222.1. Automaton of the $𝚕𝚎𝚡_𝚋𝚎𝚝𝚠𝚎𝚎𝚗$ constraint

Figure 5.222.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚕𝚎𝚡_𝚋𝚎𝚝𝚠𝚎𝚎𝚗$ constraint (since all states of the automaton are accepting there is no restriction on the last variable $Q_{n}$ )

Global Constraint Catalog

5. Global Constraint Catalogue

5.222. lex_between

Figure 5.222.1. Automaton of the 𝚕𝚎𝚡_𝚋𝚎𝚝𝚠𝚎𝚎𝚗 constraint

Figure 5.222.2. Hypergraph of the reformulation corresponding to the automaton of the 𝚕𝚎𝚡_𝚋𝚎𝚝𝚠𝚎𝚎𝚗 constraint (since all states of the automaton are accepting there is no restriction on the last variable Q n )

Figure 5.222.1. Automaton of the $𝚕𝚎𝚡_𝚋𝚎𝚝𝚠𝚎𝚎𝚗$ constraint

Figure 5.222.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚕𝚎𝚡_𝚋𝚎𝚝𝚠𝚎𝚎𝚗$ constraint (since all states of the automaton are accepting there is no restriction on the last variable $Q_{n}$ )