Global Constraint Catalog: Cstretch_path

5.377. stretch_path_partition

DESCRIPTION

LINKS

Origin

Derived from $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑$ .

Constraint

$𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂)$

Synonym

$𝚜𝚝𝚛𝚎𝚝𝚌𝚑$ .

Type

𝚅𝙰𝙻𝚄𝙴𝚂

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

Arguments

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚙 - 𝚅𝙰𝙻𝚄𝙴𝚂, 𝚕𝚖𝚒𝚗 - 𝚒𝚗𝚝, 𝚕𝚖𝚊𝚡 - 𝚒𝚗𝚝)$

Restrictions

| 𝚅𝙰𝙻𝚄𝙴𝚂 | \geq 1

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝙻𝚄𝙴𝚂, 𝚟𝚊𝚕)

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

(𝚅𝙰𝙻𝚄𝙴𝚂, 𝚟𝚊𝚕)

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

| 𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂 | > 0

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂, [𝚙, 𝚕𝚖𝚒𝚗, 𝚕𝚖𝚊𝚡])

𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂 . 𝚕𝚖𝚒𝚗 \geq 0

𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂 . 𝚕𝚖𝚒𝚗 \leq 𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂 . 𝚕𝚖𝚊𝚡

𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂 . 𝚕𝚖𝚒𝚗 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

Purpose

In order to define the meaning of the $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint, we first introduce the notions of stretch and span. Let $n$ be the number of variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ . Let $X_{i}, \dots, X_{j}$ $(1 \leq i \leq j \leq n)$ be consecutive variables of the collection of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ such that the following conditions apply:

All variables $X_{i}, \dots, X_{j}$ take their values in the same partition of the $𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂$ collection (i.e., $\exists l \in [1, | 𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂 |]$ such that $\forall k \in [i, j] : X_{k} \in 𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂 [l] . p$ ),
$i = 1$ or $X_{i - 1}$ is different from $X_{i}$ ,
$j = n$ or $X_{j + 1}$ is different from $X_{j}$ .

We call such a set of variables a stretch. The span of the stretch is equal to $j - i + 1$ , while the value of the stretch is $l$ . We now define the condition enforced by the $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint.

Each item $𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂 [l] = (𝚙 - 𝑣𝑎𝑙𝑢𝑒𝑠, 𝚕𝚖𝚒𝚗 - s, 𝚕𝚖𝚊𝚡 - t)$ of the $𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂$ collection enforces the minimum value $s$ as well as the maximum value $t$ for the span of a stretch of value $l$ over consecutive variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection.

Note that:

Having an item $𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂 [l] = (𝚙 - 𝑣𝑎𝑙𝑢𝑒𝑠, 𝚕𝚖𝚒𝚗 - s, 𝚕𝚖𝚊𝚡 - t)$ with $s$ strictly greater than 0 does not mean that values of $𝑣𝑎𝑙𝑢𝑒𝑠$ should be assigned to one of the variables of collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ . It rather means that, when a value of $𝑣𝑎𝑙𝑢𝑒𝑠$ is used, all stretches of value $l$ must have a span that belong to interval $[s, t]$ .
A variable of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ may be assigned a value that is not defined in the attribute $𝚙$ of the $𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂$ collection.

Example

(\begin{matrix} 〈1, 2, 0, 0, 2, 2, 2, 0〉, \\ 〈\begin{matrix} 𝚙 - 〈1, 2〉 & 𝚕𝚖𝚒𝚗 - 2 & 𝚕𝚖𝚊𝚡 - 4, \\ 𝚙 - 〈3〉 & 𝚕𝚖𝚒𝚗 - 0 & 𝚕𝚖𝚊𝚡 - 2 \end{matrix}〉 \end{matrix})

The $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint holds since the sequence $12002220$ contains two stretches $12$ , and $222$ respectively verifying the following conditions:

The span of the first stretch $12$ is located within interval $[2, 4]$ (i.e., the limit associated with item $𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂 [1]$ ).
The span of the second stretch $222$ is located within interval $[2, 4]$ (i.e., the limit associated with item $𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂 [1]$ ).

Typical

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

𝚛𝚊𝚗𝚐𝚎

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

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > | 𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂 |

| 𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂 | > 1

𝚜𝚞𝚖

(𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂 . 𝚕𝚖𝚒𝚗) \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂 . 𝚕𝚖𝚊𝚡 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

Symmetries

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ can be reversed.
Items of $𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂$ are permutable.
Items of $𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂 . 𝚙$ are permutable.
All occurrences of two distinct tuples of values in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ or $𝙿𝙰𝚁𝙻𝙸𝙼𝙸𝚃𝚂 . 𝚙 . 𝚟𝚊𝚕$ can be swapped; all occurrences of a tuple of values in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ or $𝙿𝙰𝚁𝙻𝙸𝙼𝙸𝚃𝚂 . 𝚙 . 𝚟𝚊𝚕$ can be renamed to any unused tuple of values.

specialisation: $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 \in 𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ ).

Keywords

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

combinatorial object: sequence.

constraint network structure: Berge-acyclic constraint network.

constraint type: timetabling constraint, sliding sequence constraint.

filtering: arc-consistency.

final graph structure: consecutive loops are connected.

Global Constraint Catalog

5. Global Constraint Catalogue

5.377. stretch_path_partition