Global Constraint Catalog: Cstretch

5.376. stretch_path

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

[Pesant01]

Constraint

$𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚅𝙰𝙻𝚄𝙴𝚂)$

Usual name

$𝚜𝚝𝚛𝚎𝚝𝚌𝚑$

Arguments

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

Restrictions

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > 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 a same value from the set of values of the $𝚟𝚊𝚕$ attribute,
$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 $X_{i}$ . We now define the condition enforced by the $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑$ constraint.

Each item $(𝚟𝚊𝚕 - v, 𝚕𝚖𝚒𝚗 - 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 $v$ over consecutive variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection.

Note that:

Having an item $(𝚟𝚊𝚕 - v, 𝚕𝚖𝚒𝚗 - s, 𝚕𝚖𝚊𝚡 - t)$ with $s$ strictly greater than 0 does not mean that value $v$ should be assigned to one of the variables of collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ . It rather means that, when value $v$ is used, all stretches of value $v$ 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 $𝚅𝙰𝙻𝚄𝙴𝚂$ collection.

Example

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

The $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑$ constraint holds since the sequence $66311166$ contains four stretches $66$ , 3, $111$ , and $66$ respectively verifying the following conditions:

The span of the first stretch $66$ is located within interval $[2, 2]$ (i.e., the limit associated with value 6).
The span of the second stretch 3 is located within interval $[1, 6]$ (i.e., the limit associated with value 3).
The span of the third stretch $111$ is located within interval $[2, 4]$ (i.e., the limit associated with value 1).
The span of the fourth stretch $66$ is located within interval $[2, 2]$ (i.e., the limit associated with value 6).

Typical

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

𝚛𝚊𝚗𝚐𝚎

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

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

| 𝚅𝙰𝙻𝚄𝙴𝚂 | > 1

𝚜𝚞𝚖

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

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

Symmetries

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ can be reversed.
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

The article [Pesant01], which originally introduced the $𝚜𝚝𝚛𝚎𝚝𝚌𝚑$ constraint, quotes rostering problems as typical examples of use of this constraint.

Remark

We split the original $𝚜𝚝𝚛𝚎𝚝𝚌𝚑$ constraint into the $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑$ and the $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚌𝚒𝚛𝚌𝚞𝚒𝚝$ constraints that respectively use the $𝑃𝐴𝑇𝐻$ $𝐿𝑂𝑂𝑃$ and the $𝐶𝐼𝑅𝐶𝑈𝐼𝑇$ $𝐿𝑂𝑂𝑃$ arc generators. We also reorganise the parameters: the $𝚅𝙰𝙻𝚄𝙴𝚂$ collection describes the attributes of each value that can be assigned to the variables of the $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑$ constraint. Finally we skipped the pattern constraint that tells what values can follow a given value. A extension of this constraint (i.e., stretch plus pattern), called $𝚏𝚘𝚛𝚌𝚎𝚍_𝚜𝚑𝚒𝚏𝚝_𝚜𝚝𝚛𝚎𝚝𝚌𝚑$ , where one can specify for each value $v$ with a 0-1 variable, whether it should occur at least once or not at all, was proposed in [HellstenPesantBeek04]. By reduction to Hamiltonian path it was shown that enforcing arc-consistency for $𝚏𝚘𝚛𝚌𝚎𝚍_𝚜𝚑𝚒𝚏𝚝_𝚜𝚝𝚛𝚎𝚝𝚌𝚑$ is NP-hard [HellstenPesantBeek04].

Algorithm

A first filtering algorithm was described in the original article of G. Pesant [Pesant01]. A second filtering algorithm, based on dynamic programming, achieving arc-consistency is depicted in [Hellsten04], [HellstenPesantBeek04]. It also handles the fact that some values can be followed by only a given subset of values. An other alternative achieving arc-consistency is to use the automaton described in the Automaton slot.

Systems

stretchPath in Choco, stretch in JaCoP.

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

uses in its reformulation: $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚌𝚒𝚛𝚌𝚞𝚒𝚝$ .

Keywords

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

combinatorial object: sequence.

constraint network structure: Berge-acyclic constraint network.

constraint type: timetabling constraint, sliding sequence constraint.

filtering: dynamic programming, arc-consistency.

final graph structure: consecutive loops are connected.

For all items of $𝚅𝙰𝙻𝚄𝙴𝚂$ :

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝑃𝐴𝑇𝐻

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

𝐿𝑂𝑂𝑃

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

Arc arity

Arc constraint(s)

• 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛 = 𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕

• 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛 = 𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕

Graph property(ies)

•

𝚗𝚘𝚝_𝚒𝚗

(

𝐌𝐈𝐍_𝐍𝐂𝐂

, 1, 𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚕𝚖𝚒𝚗 - 1)

•

𝐌𝐀𝐗_𝐍𝐂𝐂

\leq 𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚕𝚖𝚊𝚡

Graph model

Part (A) of Figure 5.376.1 shows the initial graphs associated with values 1, 2, 3 and 6 of the Example slot. Part (B) of Figure 5.376.1 shows the corresponding final graphs associated with values 1, 3 and 6. Since value 2 is not assigned to any variable of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection the final graph associated with value 2 is empty. The $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑$ constraint holds since:

For value 1 we have one connected component for which the number of vertices 3 is greater than or equal to 2 and less than or equal to 4,
For value 2 we do not have any connected component,
For value 3 we have one connected component for which the number of vertices 1 is greater than or equal to 1 and less than or equal to 6,
For value 6 we have two connected components that both contain two vertices: this is greater than or equal to 2 and less than or equal to 2.

Figure 5.376.1. Initial and final graph of the $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑$ constraint


(a)	(b)

During the presentation of this constraint at CP'2001 the following point was mentioned: it could be useful to allow domain variables for the minimum and the maximum values of a stretch. This could be achieved in the following way: the $𝚕𝚖𝚒𝚗$ (respectively $𝚕𝚖𝚊𝚡$ ) attribute would now be a domain variable that gives the size of the shortest (respectively longest) stretch. Finally within the Graph property(ies) slot we would replace $\geq$ (and $\leq$ ) by $=$ .

Automaton

Let $n$ and $m$ respectively denote the quantities $| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |$ and $| 𝚅𝙰𝙻𝚄𝙴𝚂 |$ . Furthermore, let ${𝚟𝚊𝚕}_{i}$ , ${𝚕𝚖𝚒𝚗}_{i}$ and ${𝚕𝚖𝚊𝚡}_{i}$ , $(i \in [1, m])$ , respectively be shortcuts for the expressions $𝚅𝙰𝙻𝚄𝙴𝚂 [i] . 𝚟𝚊𝚕$ , $𝚅𝙰𝙻𝚄𝙴𝚂 [i] . 𝚕𝚖𝚒𝚗$ and $𝚅𝙰𝙻𝚄𝙴𝚂 [i] . 𝚕𝚖𝚊𝚡$ . Without loss of generality, we assume that all the $𝚕𝚖𝚒𝚗$ attributes of the items of the $𝚅𝙰𝙻𝚄𝙴𝚂$ collection are at least equal to 1. The following automaton $𝒜$ involving $1 + {𝚕𝚖𝚊𝚡}_{1} + {𝚕𝚖𝚊𝚡}_{2} + \dots + {𝚕𝚖𝚊𝚡}_{m}$ states only accepts solutions to the $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑$ constraint. Automaton $𝒜$ has the following states:

an initial state $s$ that is also an accepting state,
$\forall i \in [1, m], \forall j \in [1, {𝚕𝚖𝚒𝚗}_{i} - 1]$ , a non-accepting state $s_{i, j}$ ,
$\forall i \in [1, m], \forall j \in [{𝚕𝚖𝚒𝚗}_{i}, {𝚕𝚖𝚊𝚡}_{i}]$ , an accepting state $s_{i, j}$ .

Transitions of $𝒜$ are defined in the following way:

$\forall i \in [1, m]$ , a transition from $s$ to $s_{i, 1}$ labelled by condition $X_{l} = {𝚟𝚊𝚕}_{i}$ ,
a transition from $s$ to $s$ labelled by condition $X_{l} \neq {𝚟𝚊𝚕}_{1} \land X_{l} \neq {𝚟𝚊𝚕}_{2} \land \dots \land X_{l} \neq {𝚟𝚊𝚕}_{m}$ ,
$\forall i \in [1, m], \forall j \in [{𝚕𝚖𝚒𝚗}_{i}, {𝚕𝚖𝚊𝚡}_{i}]$ , a transition from $s_{i, j}$ to $s$ labelled by condition $X_{l} \neq {𝚟𝚊𝚕}_{1} \land X_{l} \neq {𝚟𝚊𝚕}_{2} \land \dots \land X_{l} \neq {𝚟𝚊𝚕}_{m}$ ,
$\forall i \in [1, m], \forall j \in [1, {𝚕𝚖𝚊𝚡}_{i} - 1]$ , a transition from $s_{i, j}$ to $s_{i, j + 1}$ labelled by condition $X_{l} = {𝚟𝚊𝚕}_{i}$ ,
$\forall i \in [1, m], \forall j \in [{𝚕𝚖𝚒𝚗}_{i}, {𝚕𝚖𝚊𝚡}_{i}], \forall k \neq i \in [1, m]$ , a transition from $s_{i, j}$ to $s_{k, 1}$ labelled by condition $X_{l} = {𝚟𝚊𝚕}_{k}$ .

Figure 5.376.2 depicts the automaton associated with the $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑$ constraint of the Example slot. Transitions labels 0, 1, 2, 3 and 4 respectively correspond to the conditions $X_{l} \neq 1 \land X_{l} \neq 2 \land X_{l} \neq 3 \land X_{l} \neq 6$ , $X_{l} = 1$ , $X_{l} = 2$ , $X_{l} = 3$ , $X_{l} = 6$ (since values 1, 2, 3 and 6 respectively correspond to the values of the first, second, third and fourth item of the $𝚅𝙰𝙻𝚄𝙴𝚂$ collection). The $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑$ constraint holds since the corresponding sequence of visited states, $s$ $s_{41}$ $s_{42}$ $s_{31}$ $s_{11}$ $s_{12}$ $s_{13}$ $s_{41}$ $s_{42}$ , ends up in an accepting state (i.e., accepting states are denoted graphically by a double circle in the figure).

Figure 5.376.2. Automaton of the $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑$ constraint of the Example slot (states related to a same stretch have the same colour)

Global Constraint Catalog

5. Global Constraint Catalogue

5.376. stretch_path

Figure 5.376.1. Initial and final graph of the 𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑 constraint

Figure 5.376.2. Automaton of the 𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑 constraint of the Example slot (states related to a same stretch have the same colour)

Figure 5.376.1. Initial and final graph of the $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑$ constraint

Figure 5.376.2. Automaton of the $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑$ constraint of the Example slot (states related to a same stretch have the same colour)