Specifications PyCSP³ Tools Instances Competitions About

Constraint stretch

The constraint stretch [P01] aims at grouping values in sequences. Each stretch is a maximal subsequence with the same value over the list of variables in list. Each stretch must have a width compatible with the corresponding interval specified in widths. The optional element patterns gives the possible successive values between stretches.</p>

Given a sequence of variables $X=\langle x_1,x_2,\ldots \rangle$, and a value assigned to each of these variables, we define as $\texttt{ST}(X)$ the set of stretches over $X$, each one being identified by a pair $(v_k,i..j)$ composed of the value $v_k$ of the stretch and the interval $i..j$ of the indexes of the variables composing the stretch.

stretch($X$, $V$, $W$) with $X=\langle x_1,x_2,\ldots \rangle$ $V=\langle v_1,v_2,\ldots \rangle$ and $W=\langle l_1..u_1,l_2..u_2,\ldots \rangle$, iff $\forall (v_k,i..j) \in \texttt{ST}(X), l_k \leq j-i+1 \leq u_k$
stretch($X$, $V$, $W$, $P$), iff stretch($X$, $V$, $W$) and $\forall i : 1 \leq i \lt |X|, x_i \neq x_{i + 1} \Rightarrow (x_i,x_{i + 1}) \in P$

Syntax

<stretch>
  <list> (intVar wspace)2+ </list>
  <values> (intVal wspace)+ </values>
  <widths> (intIntvl wspace)+ </widths>
  [<patterns> ("(" intVal "," intVal ")")+ </patterns>]
</stretch>

For the example, just imagine that values 1,2,3 and 0 represent “morning”,”afternoon”,”night” and “off” for a duty roster.

Example

<stretch>
  <list> x1 x2 x3 x4 x5 x6 x7 </list>
  <values> 1 2 3 0 </values>
  <widths> 1..3 1..3 2..3 2..4 </widths>
</stretch>

In the future, we might authorize longer forms of patterns.