[Pesant01]

$\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}\_\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂})$

$\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}$

The $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}\_\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ constraint holds since the sequence $66311166$ contains three stretches $6666$, 3, and $111$ respectively verifying the following conditions:

• The span of the first stretch $6666$ is located within interval $[2,4]$ (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).

• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ can be shifted.

• Items of $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ are permutable.

• All occurrences of two distinct values in $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ or $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}$ can be swapped; all occurrences of a value in $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ or $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}$ can be renamed to any unused value.

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

We split the origin $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}$ constraint into the $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}\_\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ and the $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}\_\mathrm{𝚙𝚊𝚝𝚑}$ constraints that respectively use the $\mathrm{𝑃𝐴𝑇𝐻}$ $\mathrm{𝐿𝑂𝑂𝑃}$ and $\mathrm{𝐶𝐼𝑅𝐶𝑈𝐼𝑇}$ $\mathrm{𝐿𝑂𝑂𝑃}$ arc generators. We also reorganise the parameters: the $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ collection describes the attributes of each value that can be assigned to the variables of the $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}\_\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ constraint. Finally we skipped the pattern constraint that tells what values can follow a given value.

A first filtering algorithm was described in the original article of G. Pesant [Pesant01]. An algorithm that also generates explanations is given in [RochartJussien03]. The first filtering algorithm achieving arc-consistency is depicted in [Hellsten04], [HellstenPesantBeek04]. This algorithm is based on dynamic programming and handles the fact that some values can be followed by only a given subset of values.

The $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}\_\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ constraint can be reformulated in term of a $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}\_\mathrm{𝚙𝚊𝚝𝚑}$ constraint. Let $\mathrm{𝐿𝑀𝐴𝑋}$ denote the maximum value taken by the $\mathrm{𝚕𝚖𝚊𝚡}$ attribute within the items of the collection $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$, let $n$ be the number of variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$, and let $\delta =min(\mathrm{𝐿𝑀𝐴𝑋},n)$. The first and second arguments of the $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}\_\mathrm{𝚙𝚊𝚝𝚑}$ constraint are created in the following way:

• We pass to the $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}\_\mathrm{𝚙𝚊𝚝𝚑}$ the variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ to which we add the $\delta$ first variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

• We pass to the $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}\_\mathrm{𝚙𝚊𝚝𝚑}$ the values of the collection $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ with the following modification: to each value $v$ for which the corresponding $\mathrm{𝚕𝚖𝚊𝚡}$ attribute is greater than or equal to $n$ we reset its value to $n+\delta$.

Even if $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}\_\mathrm{𝚙𝚊𝚝𝚑}$ can achieve arc-consistency this reformulation may not achieve arc-consistency since it duplicates variables.

Using this reformulation, the example

   $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}\_\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$$(\langle 6,6,3,1,1,1,6,6\rangle ,$

                       $\langle \mathrm{𝚟𝚊𝚕}-1\mathrm{𝚕𝚖𝚒𝚗}-2\mathrm{𝚕𝚖𝚊𝚡}-4,\mathrm{𝚟𝚊𝚕}-2\mathrm{𝚕𝚖𝚒𝚗}-2\mathrm{𝚕𝚖𝚊𝚡}-3,$

                        $\mathrm{𝚟𝚊𝚕}-3\mathrm{𝚕𝚖𝚒𝚗}-1\mathrm{𝚕𝚖𝚊𝚡}-6,\mathrm{𝚟𝚊𝚕}-6\mathrm{𝚕𝚖𝚒𝚗}-2\mathrm{𝚕𝚖𝚊𝚡}-4\rangle )$

of the Example slot is reformulated as:

   $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}\_\mathrm{𝚙𝚊𝚝𝚑}$$(\langle 6,6,3,1,1,1,6,6,6,6,3,1,1,1\rangle ,$

                   $\langle \mathrm{𝚟𝚊𝚕}-1\mathrm{𝚕𝚖𝚒𝚗}-2\mathrm{𝚕𝚖𝚊𝚡}-4,\mathrm{𝚟𝚊𝚕}-2\mathrm{𝚕𝚖𝚒𝚗}-2\mathrm{𝚕𝚖𝚊𝚡}-3,$

                    $\mathrm{𝚟𝚊𝚕}-3\mathrm{𝚕𝚖𝚒𝚗}-1\mathrm{𝚕𝚖𝚊𝚡}-6,\mathrm{𝚟𝚊𝚕}-6\mathrm{𝚕𝚖𝚒𝚗}-2\mathrm{𝚕𝚖𝚊𝚡}-4\rangle )$

In the reformulation $\delta$ was equal to 6, and the $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ collection was left unchanged since no $\mathrm{𝚕𝚖𝚊𝚡}$ attribute was equal to the number of variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection (i.e., 8).

common keyword: $\mathrm{𝚐𝚛𝚘𝚞𝚙}$ (timetabling constraint),

$\mathrm{𝚙𝚊𝚝𝚝𝚎𝚛𝚗}$ (sliding sequence constraint,timetabling constraint),

$\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}\_\mathrm{𝚍𝚒𝚜𝚝𝚛𝚒𝚋𝚞𝚝𝚒𝚘𝚗}$ (sliding sequence constraint), $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}\_\mathrm{𝚙𝚊𝚝𝚑}$ (sliding sequence constraint,timetabling constraint).

used in reformulation: $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}\_\mathrm{𝚙𝚊𝚝𝚑}$.

characteristic of a constraint: cyclic.

constraint type: timetabling constraint, sliding sequence constraint.

filtering: dynamic programming, arc-consistency, duplicated variables.

For all items of $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$: