## 5.21. among_seq

Origin
Constraint

$\mathrm{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚜𝚎𝚚}\left(\mathrm{𝙻𝙾𝚆},\mathrm{𝚄𝙿},\mathrm{𝚂𝙴𝚀},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\right)$

Synonym

$\mathrm{𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎}$.

Arguments
 $\mathrm{𝙻𝙾𝚆}$ $\mathrm{𝚒𝚗𝚝}$ $\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 \mathrm{𝙻𝙾𝚆}$ $\mathrm{𝚂𝙴𝚀}>0$ $\mathrm{𝚂𝙴𝚀}\ge \mathrm{𝙻𝙾𝚆}$ $\mathrm{𝚂𝙴𝚀}\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂},\mathrm{𝚟𝚊𝚕}\right)$ $\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$$\left(\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂},\mathrm{𝚟𝚊𝚕}\right)$
Purpose

Constrains all sequences of $\mathrm{𝚂𝙴𝚀}$ consecutive variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ to take at least $\mathrm{𝙻𝙾𝚆}$ values in $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ and at most $\mathrm{𝚄𝙿}$ values in $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$.

Example
$\left(\begin{array}{c}1,2,4,〈\begin{array}{c}\mathrm{𝚟𝚊𝚛}-9,\hfill \\ \mathrm{𝚟𝚊𝚛}-2,\hfill \\ \mathrm{𝚟𝚊𝚛}-4,\hfill \\ \mathrm{𝚟𝚊𝚛}-5,\hfill \\ \mathrm{𝚟𝚊𝚛}-5,\hfill \\ \mathrm{𝚟𝚊𝚛}-7,\hfill \\ \mathrm{𝚟𝚊𝚛}-2\hfill \end{array}〉,\hfill \\ 〈0,2,4,6,8〉\hfill \end{array}\right)$

The $\mathrm{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚜𝚎𝚚}$ constraint holds since the different sequences of 4 consecutive variables contains respectively 2, 2, 1 and 1 even numbers.

Typical
 $\mathrm{𝙻𝙾𝚆}<\mathrm{𝚂𝙴𝚀}$ $\mathrm{𝚄𝙿}>0$ $\mathrm{𝚂𝙴𝚀}>1$ $\mathrm{𝚂𝙴𝚀}<|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>1$ $|\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|>0$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>|\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|$
Symmetries
• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ can be reversed.

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

• $\mathrm{𝙻𝙾𝚆}$ can be decreased to any value $\ge 0$.

• $\mathrm{𝚄𝙿}$ can be increased to any value $\le \mathrm{𝚂𝙴𝚀}$.

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

Usage

The $\mathrm{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚜𝚎𝚚}$ constraint occurs in many timetabling problems. As a typical example taken from [HoevePesantRousseauSabharwal06], consider for instance a nurse -rostering problem where each nurse can work at most 2 night shifts during every period of 7 consecutive days.

Algorithm

Beldiceanu and Carlsson [BeldiceanuCarlsson01] have proposed a first incomplete filtering algorithm for the $\mathrm{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚜𝚎𝚚}$ constraint. Later on, W.-J. van Hoeve et al. proposed two filtering algorithms [HoevePesantRousseauSabharwal06] establishing arc-consistency as well as an incomplete filtering algorithm based on dynamic programming concepts. In 2007 Brand et al. came up with a reformulation [BrandNarodytskaQuimperStuckeyWalsh07] that provides a complete filtering algorithm. One year later, Maher et al. use a reformulation in term of a linear program [MaherNarodytskaQuimperWalsh08] where (1) each coefficient is an integer in $\left\{-1,0,1\right\}$, (2) each column has a block of consecutive 1's or $-1$'s. From this reformulation they derive a flow model that leads to an algorithm that achieves a complete filtering in $O\left({n}^{2}\right)$ along a branch of the search tree.

Systems

generalisation: $\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚍𝚒𝚜𝚝𝚛𝚒𝚋𝚞𝚝𝚒𝚘𝚗}$ (single set of values replaced by individual values).

Keywords
Arc input(s)

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

Arc generator
$\mathrm{𝑃𝐴𝑇𝐻}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}$

Arc arity
$\mathrm{𝚂𝙴𝚀}$
Arc constraint(s)
$\mathrm{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$$\left(\mathrm{𝙻𝙾𝚆},\mathrm{𝚄𝙿},\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗},\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\right)$
Graph property(ies)
$\mathrm{𝐍𝐀𝐑𝐂}$$=|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|-\mathrm{𝚂𝙴𝚀}+1$

Graph model

A constraint on sliding sequences of consecutive variables. Each vertex of the graph corresponds to a variable. Since they link $\mathrm{𝚂𝙴𝚀}$ variables, the arcs of the graph correspond to hyperarcs. In order to link $\mathrm{𝚂𝙴𝚀}$ consecutive variables we use the arc generator $\mathrm{𝑃𝐴𝑇𝐻}$. The constraint associated with an arc corresponds to the $\mathrm{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ constraint defined at another entry of this catalogue.

Signature

Since we use the $\mathrm{𝑃𝐴𝑇𝐻}$ arc generator with an arity of $\mathrm{𝚂𝙴𝚀}$ on the items of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection, the expression $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|-\mathrm{𝚂𝙴𝚀}+1$ corresponds to the maximum number of arcs of the final graph. Therefore we can rewrite the graph property $\mathrm{𝐍𝐀𝐑𝐂}$ $=$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|-\mathrm{𝚂𝙴𝚀}+1$ to $\mathrm{𝐍𝐀𝐑𝐂}$ $\ge$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|-\mathrm{𝚂𝙴𝚀}+1$ and simplify $\underline{\overline{\mathrm{𝐍𝐀𝐑𝐂}}}$ to $\overline{\mathrm{𝐍𝐀𝐑𝐂}}$.