5.266. pattern

DESCRIPTIONLINKSAUTOMATON
Origin

[BourdaisGalinierPesant03]

Constraint

πš™πšŠπšπšπšŽπš›πš—(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,π™Ώπ™°πšƒπšƒπ™΄πšπ™½πš‚)

Type
π™Ώπ™°πšƒπšƒπ™΄πšπ™½πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πš’πš—πš)
Arguments
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
π™Ώπ™°πšƒπšƒπ™΄πšπ™½πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš™πšŠπš-π™Ώπ™°πšƒπšƒπ™΄πšπ™½)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(π™Ώπ™°πšƒπšƒπ™΄πšπ™½,πšŸπšŠπš›)
π™Ώπ™°πšƒπšƒπ™΄πšπ™½.πšŸπšŠπš›β‰₯0
πšŒπš‘πšŠπš—πšπšŽ(0,π™Ώπ™°πšƒπšƒπ™΄πšπ™½,=)
|π™Ώπ™°πšƒπšƒπ™΄πšπ™½|>1
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(π™Ώπ™°πšƒπšƒπ™΄πšπ™½πš‚,πš™πšŠπš)
|π™Ώπ™°πšƒπšƒπ™΄πšπ™½πš‚|>0
πšœπšŠπš–πšŽ_πšœπš’πš£πšŽ(π™Ώπ™°πšƒπšƒπ™΄πšπ™½πš‚,πš™πšŠπš)
Purpose

We quote the definition from the original articleΒ [BourdaisGalinierPesant03] introducing the πš™πšŠπšπšπšŽπš›πš— constraint:

β€œWe call a k-pattern (k>1) any sequence of k elements such that no two successive elements have the same value. Consider a set V={v 1 ,v 2 ,...,v m } and a sequence 𝐬=s 1 s 2 ... s n of elements of V. In this context, a stretch is a maximum subsequence of variables of 𝐬 which all have the same value. Consider now the sequence v i 1 v i 2 ... v i l of the types of the successive stretches that appear in 𝐬. Let 𝒫 be a set of k-patterns. 𝐬 satisfies 𝒫 if and only if every subsequence of k elements in v i 1 v i 2 ...,v i l belongs to 𝒫.”

Example
πšŸπšŠπš›-1,πšŸπšŠπš›-1,πšŸπšŠπš›-2,πšŸπšŠπš›-2,πšŸπšŠπš›-2,πšŸπšŠπš›-1,πšŸπšŠπš›-3,πšŸπšŠπš›-3,πš™πšŠπš-1,2,1,πš™πšŠπš-1,2,3,πš™πšŠπš-2,1,3

The πš™πšŠπšπšπšŽπš›πš— constraint holds since, as depicted by FigureΒ 5.266.1, all its sequences of three consecutive stretches correspond to one of the 3-pattern given in the π™Ώπ™°πšƒπšƒπ™΄πšπ™½πš‚ collection.

Figure 5.266.1. The sequence of the Example slot, its four stretches and the corresponding two 3-patterns 1 2 1 and 2 1 3
ctrs/pattern1
Symmetries
  • Items of π™Ώπ™°πšƒπšƒπ™΄πšπ™½πš‚ are permutable.

  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ and π™Ώπ™°πšƒπšƒπ™΄πšπ™½πš‚.πš™πšŠπš are simultaneously reversable.

  • 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.

Usage

The πš™πšŠπšπšπšŽπš›πš— constraint was originally introduced within the context of staff scheduling. In this context, the value of the i th variable of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection corresponds to the type of shift performed by a person on the i th day. A stretch is a maximum sequence of consecutive variables that are all assigned to the same value. The πš™πšŠπšπšπšŽπš›πš— constraint imposes that each sequence of k consecutive stretches belongs to a given list of patterns.

Remark

A generalisation of the πš™πšŠπšπšπšŽπš›πš— constraint to the πš›πšŽπšπšžπš•πšŠπš› constraint enforcing the fact that a sequence of variables corresponds to a regular expression is presented inΒ [Pesant04].

See also

common keyword: πšπš›πš˜πšžπš™Β (timetabling constraint),

πšœπš•πš’πšπš’πš—πš_πšπš’πšœπšπš›πš’πš‹πšžπšπš’πš˜πš—Β (sliding sequence constraint),

πšœπšπš›πšŽπšπšŒπš‘_πšŒπš’πš›πšŒπšžπš’πš, πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘Β (sliding sequence constraint,timetabling constraint),

πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘_πš™πšŠπš›πšπš’πšπš’πš˜πš—Β (sliding sequence constraint).

Keywords

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

constraint network structure: Berge-acyclic constraint network.

constraint type: predefined constraint, timetabling constraint, sliding sequence constraint.

filtering: arc-consistency.

Automaton

Taking advantage of the fact that all k-patterns have the same length k, it is straightforward to construct an automaton that only accepts solutions of the πš™πšŠπšπšπšŽπš›πš— constraint. FigureΒ 5.266.2 depicts the automaton associated with the πš™πšŠπšπšπšŽπš›πš— constraint of the Example slot. The construction can be done in three steps:

  • First, build a prefix tree of all the k-patterns. In the context of our example, this gives all arcs of FigureΒ 5.266.2, except self loops and the arc from s 3 to s 7 .

  • Second, find out the transitions that exit a leave of the tree. For this purpose we remove the first symbol of the corresponding k-pattern, add at the end of the remaining k-pattern a symbol corresponding to a stretch value, and check whether the new pattern belongs or not to the set of k-patterns of the πš™πšŠπšπšπšŽπš›πš— constraint. When the new pattern belongs to the set of k-patterns we add a corresponding transition. For instance, in the context of our example, consider the leave s 3 that is associated with the 3-pattern 1,2,1. We remove the first symbol 1 and get 2,1. We then try to successively add the stretch values 1, 2 and 3 to the end of 2,1 and check if the corresponding patterns 2,1,1,Β Β 2,1,2 and 2,1,3 belong or not to our set of 3-patterns. Since only 2,1,3 is a 3-pattern we add a new transition between the corresponding leaves of the prefix tree (i.e.,Β a transition from s 3 to s 7 ).

  • Third, in order to take into account the fact that each value of a k-pattern corresponds in fact to a given stretch value (i.e.,Β several consecutive values that are assigned the same value), we add a self loop to all non -source states with a transition label that corresponds to the transition label of their entering arc.

Figure 5.266.2. Automaton of the πš™πšŠπšπšπšŽπš›πš— constraint of the Example slot
ctrs/pattern2