## 5.349. sliding_card_skip0

Origin

N. Beldiceanu

Constraint

$\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚌𝚊𝚛𝚍}_\mathrm{𝚜𝚔𝚒𝚙}\mathtt{0}\left(\mathrm{𝙰𝚃𝙻𝙴𝙰𝚂𝚃},\mathrm{𝙰𝚃𝙼𝙾𝚂𝚃},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\right)$

Arguments
 $\mathrm{𝙰𝚃𝙻𝙴𝙰𝚂𝚃}$ $\mathrm{𝚒𝚗𝚝}$ $\mathrm{𝙰𝚃𝙼𝙾𝚂𝚃}$ $\mathrm{𝚒𝚗𝚝}$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚕}-\mathrm{𝚒𝚗𝚝}\right)$
Restrictions
 $\mathrm{𝙰𝚃𝙻𝙴𝙰𝚂𝚃}\ge 0$ $\mathrm{𝙰𝚃𝙻𝙴𝙰𝚂𝚃}\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $\mathrm{𝙰𝚃𝙼𝙾𝚂𝚃}\ge 0$ $\mathrm{𝙰𝚃𝙼𝙾𝚂𝚃}\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $\mathrm{𝙰𝚃𝙼𝙾𝚂𝚃}\ge \mathrm{𝙰𝚃𝙻𝙴𝙰𝚂𝚃}$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂},\mathrm{𝚟𝚊𝚕}\right)$ $\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$$\left(\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂},\mathrm{𝚟𝚊𝚕}\right)$ $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}\ne 0$
Purpose

Let $n$ be the total number of variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$. A maximum non-zero set of consecutive variables ${X}_{i}..{X}_{j}\left(1\le i\le j\le n\right)$ is defined in the following way:

• All variables ${X}_{i},\cdots ,{X}_{j}$ take a non-zero value,

• $i=1$ or ${X}_{i-1}$ is equal to 0,

• $j=n$ or ${X}_{j+1}$ is equal to 0.

Enforces that each maximum non-zero set of consecutive variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ contains at least $\mathrm{𝙰𝚃𝙻𝙴𝙰𝚂𝚃}$ and at most $\mathrm{𝙰𝚃𝙼𝙾𝚂𝚃}$ values from the collection of values $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$.

Example
$\left(2,3,〈0,7,2,9,0,0,9,4,9〉,〈7,9〉\right)$

The $\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚌𝚊𝚛𝚍}_\mathrm{𝚜𝚔𝚒𝚙}\mathtt{0}$ constraint holds since the two maximum non-zero set of consecutive values $729$ and $949$ of its third argument $〈0,7,2,9,0,0,9,4,9〉$ take both 2 ($2\in \left[\mathrm{𝙰𝚃𝙻𝙴𝙰𝚂𝚃},\mathrm{𝙰𝚃𝙼𝙾𝚂𝚃}\right]=\left[2,3\right]$) values within the set of values $〈7,9〉$.

Typical
 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>1$ $|\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|>0$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>|\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|$ $\mathrm{𝚊𝚝𝚕𝚎𝚊𝚜𝚝}$$\left(1,\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},0\right)$ $\mathrm{𝙰𝚃𝙻𝙴𝙰𝚂𝚃}>0\vee \mathrm{𝙰𝚃𝙼𝙾𝚂𝚃}<|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$
Symmetries
• $\mathrm{𝙰𝚃𝙻𝙴𝙰𝚂𝚃}$ can be decreased to any value $\ge 0$.

• $\mathrm{𝙰𝚃𝙼𝙾𝚂𝚃}$ can be increased to any value $\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$.

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

• An occurrence of a value different from 0 of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ that belongs to $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}$ (resp. does not belong to $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}$ ) can be replaced by any other value different from 0 in $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}$ (resp. not in $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}$).

Usage

This constraint is useful in timetabling problems where the variables are interpreted as the type of job that a person does on consecutive days. Value 0 represents a rest day and one imposes a cardinality constraint on periods that are located between rest periods.

Remark

One cannot initially state a $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint since the rest days are not yet allocated. One can also not use an $\mathrm{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚜𝚎𝚚}$ constraint since it does not hold for the sequences of consecutive variables that contains at least one rest day.

related: $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ (counting constraint on the full sequence), $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ (counting constraint for different values on the full sequence).

specialisation: $\mathrm{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ (maximal sequences replaced by the full sequence).

Keywords
Arc input(s)

$\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$

Arc generator
 $\mathrm{𝑃𝐴𝑇𝐻}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}\right)$ $\mathrm{𝐿𝑂𝑂𝑃}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}\right)$

Arc arity
Arc constraint(s)
 $•\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚟𝚊𝚛}\ne 0$ $•\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\mathrm{𝚟𝚊𝚛}\ne 0$
Sets
$\mathrm{𝖢𝖢}↦\left[\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\right]$

Constraint(s) on sets
$\mathrm{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$$\left(\mathrm{𝙰𝚃𝙻𝙴𝙰𝚂𝚃},\mathrm{𝙰𝚃𝙼𝙾𝚂𝚃},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜},\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\right)$
Graph model

Note that the arc constraint will produce the different sequences of consecutive variables that do not contain any 0. The $\mathrm{𝖢𝖢}$ set generator produces all the connected components of the final graph.

Parts (A) and (B) of Figure 5.349.1 respectively show the initial and final graph associated with the Example slot. Since we use the set generator $\mathrm{𝖢𝖢}$ we show the two connected components of the final graph. Since these two connected components both contains between 2 and 3 variables that take their values in $\left\{7,9\right\}$ the $\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚌𝚊𝚛𝚍}_\mathrm{𝚜𝚔𝚒𝚙}\mathtt{0}$ constraint holds.

##### Figure 5.349.1. Initial and final graph of the $\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚌𝚊𝚛𝚍}_\mathrm{𝚜𝚔𝚒𝚙}\mathtt{0}$ constraint  (a) (b)
Automaton

Figure 5.349.2 depicts the automaton associated with the $\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚌𝚊𝚛𝚍}_\mathrm{𝚜𝚔𝚒𝚙}\mathtt{0}$ constraint. To each variable ${\mathrm{𝚅𝙰𝚁}}_{i}$ of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ corresponds a signature variable ${S}_{i}$. The following signature constraint links ${\mathrm{𝚅𝙰𝚁}}_{i}$ and ${S}_{i}$:

$\left({\mathrm{𝚅𝙰𝚁}}_{i}=0\right)⇔{S}_{i}=0\wedge$

$\left({\mathrm{𝚅𝙰𝚁}}_{i}\ne 0\wedge {\mathrm{𝚅𝙰𝚁}}_{i}\notin \mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\right)⇔{S}_{i}=1\wedge$

$\left({\mathrm{𝚅𝙰𝚁}}_{i}\ne 0\wedge {\mathrm{𝚅𝙰𝚁}}_{i}\in \mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\right)⇔{S}_{i}=2$.

##### Figure 5.349.2. Automaton of the $\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚌𝚊𝚛𝚍}_\mathrm{𝚜𝚔𝚒𝚙}\mathtt{0}$ constraint ##### Figure 5.349.3. Hypergraph of the reformulation corresponding to the automaton of the $\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚌𝚊𝚛𝚍}_\mathrm{𝚜𝚔𝚒𝚙}\mathtt{0}$ constraint 