5.318. stretch_path

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

[Pesant01]

Constraint

πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚)

Usual name

πšœπšπš›πšŽπšπšŒπš‘

Arguments
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™°π™»πš„π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•-πš’πš—πš,πš•πš–πš’πš—-πš’πš—πš,πš•πš–πšŠπš‘-πš’πš—πš)
Restrictions
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>0
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
|πš…π™°π™»πš„π™΄πš‚|>0
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°π™»πš„π™΄πš‚,[πšŸπšŠπš•,πš•πš–πš’πš—,πš•πš–πšŠπš‘])
πšπš’πšœπšπš’πš—πšŒπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
πš…π™°π™»πš„π™΄πš‚.πš•πš–πš’πš—β‰€πš…π™°π™»πš„π™΄πš‚.πš•πš–πšŠπš‘
Purpose

In order to define the meaning of the πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘ constraint, we first introduce the notions of stretch and span. Let n be the number of variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. Let X i ,...,X j (1≀i≀j≀n) be consecutive variables of the collection of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ such that the following conditions apply:

  • All variables X i ,...,X j take a same value from the set of values of the πšŸπšŠπš• attribute,

  • i=1 or X i-1 is different from X i ,

  • j=n or X j+1 is different from X j .

We call such a set of variables a stretch. The span of the stretch is equal to j-i+1, while the value of the stretch is X i . We now define the condition enforced by the πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘ constraint.

Each item (πšŸπšŠπš•-v,πš•πš–πš’πš—-s,πš•πš–πšŠπš‘-t) of the πš…π™°π™»πš„π™΄πš‚ collection enforces the minimum value s as well as the maximum value t for the span of a stretch of value v over consecutive variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection.

Note that:

  1. Having an item (πšŸπšŠπš•-v,πš•πš–πš’πš—-s,πš•πš–πšŠπš‘-t) with s strictly greater than 0 does not mean that value v should be assigned to one of the variables of collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. It rather means that, when value v is used, all stretches of value v must have a span that belong to interval [s,t].

  2. A variable of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ may be assigned a value that is not defined in the πš…π™°π™»πš„π™΄πš‚ collection.

Example
πšŸπšŠπš›-6,πšŸπšŠπš›-6,πšŸπšŠπš›-3,πšŸπšŠπš›-1,πšŸπšŠπš›-1,πšŸπšŠπš›-1,πšŸπšŠπš›-6,πšŸπšŠπš›-6,πšŸπšŠπš•-1πš•πš–πš’πš—-2πš•πš–πšŠπš‘-4,πšŸπšŠπš•-2πš•πš–πš’πš—-2πš•πš–πšŠπš‘-3,πšŸπšŠπš•-3πš•πš–πš’πš—-1πš•πš–πšŠπš‘-6,πšŸπšŠπš•-6πš•πš–πš’πš—-2πš•πš–πšŠπš‘-2

The πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘ constraint holds since the sequence 6 6 3 1 1 1 6 6 contains four stretches 6 6, 3, 1 1 1, and 6 6 respectively verifying the following conditions:

  • The span of the first stretch 6 6 is located within interval [2,2] (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 1 1 1 is located within interval [2,4] (i.e.,Β the limit associated with value 1).

  • The span of the fourth stretch 6 6 is located within interval [2,2] (i.e.,Β the limit associated with value 6).

Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ can be reversed.

  • Items of πš…π™°π™»πš„π™΄πš‚ are permutable.

  • All occurrences of two distinct values in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› or πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš• can be swapped; all occurrences of a value in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› or πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš• can be renamed to any unused value.

Usage

The articleΒ [Pesant01], which originally introduced the πšœπšπš›πšŽπšπšŒπš‘ constraint, quotes rostering problems as typical examples of use of this constraint.

Remark

We split the original πšœπšπš›πšŽπšπšŒπš‘ constraint into the πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘ and the πšœπšπš›πšŽπšπšŒπš‘_πšŒπš’πš›πšŒπšžπš’πš constraints that respectively use the 𝑃𝐴𝑇𝐻 𝐿𝑂𝑂𝑃 and the πΆπΌπ‘…πΆπ‘ˆπΌπ‘‡ 𝐿𝑂𝑂𝑃 arc generators. We also reorganise the parameters: the πš…π™°π™»πš„π™΄πš‚ collection describes the attributes of each value that can be assigned to the variables of the πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘ constraint. Finally we skipped the pattern constraint that tells what values can follow a given value. A extension of this constraint (i.e.,Β stretch plus pattern), called πšπš˜πš›πšŒπšŽπš_πšœπš‘πš’πšπš_πšœπšπš›πšŽπšπšŒπš‘, where one can specify for each value v with a 0-1 variable, whether it should occur at least once or not at all, was proposed inΒ [HellstenPesantBeek04]. By reduction to Hamiltonian path it was shown that enforcing arc-consistency for πšπš˜πš›πšŒπšŽπš_πšœπš‘πš’πšπš_πšœπšπš›πšŽπšπšŒπš‘ is NP -hardΒ [HellstenPesantBeek04].

Algorithm

A first filtering algorithm was described in the original article of G.Β PesantΒ [Pesant01]. A second filtering algorithm, based on dynamic programming, achieving arc-consistency is depicted in Β [Hellsten04], [HellstenPesantBeek04]. It also handles the fact that some values can be followed by only a given subset of values. An other alternative achieving arc-consistency is to use the automaton described in the Automaton slot.

Systems

stretchPath in Choco, stretch in JaCoP.

See also

common keyword: πšŒπš‘πšŠπš—πšπšŽ_πšŒπš˜πš—πšπš’πš—πšžπš’πšπš’, πšπš›πš˜πšžπš™Β (timetabling constraint), πšπš›πš˜πšžπš™_πšœπš”πš’πš™_πš’πšœπš˜πš•πšŠπšπšŽπš_πš’πšπšŽπš–Β (timetabling constraint,sequence), πš™πšŠπšπšπšŽπš›πš—Β (sliding sequence constraint,timetabling constraint), πšœπš•πš’πšπš’πš—πš_πšπš’πšœπšπš›πš’πš‹πšžπšπš’πš˜πš—Β (sliding sequence constraint), πšœπšπš›πšŽπšπšŒπš‘_πšŒπš’πš›πšŒπšžπš’πšΒ (sliding sequence constraint,timetabling constraint).

generalisation: πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘_πš™πšŠπš›πšπš’πšπš’πš˜πš—Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽβˆˆπš™πšŠπš›πšπš’πšπš’πš˜πš—).

uses in its reformulation: πšœπšπš›πšŽπšπšŒπš‘_πšŒπš’πš›πšŒπšžπš’πš.

Keywords

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

combinatorial object: sequence.

constraint network structure: Berge-acyclic constraint network.

constraint type: timetabling constraint, sliding sequence constraint.

filtering: dynamic programming, arc-consistency.

final graph structure: consecutive loops are connected.

For all items of πš…π™°π™»πš„π™΄πš‚:

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generator
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)
πΏπ‘‚π‘‚π‘ƒβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
β€’ πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•
β€’ πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›=πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•
Graph property(ies)
β€’ πš—πš˜πš_πš’πš—(𝐌𝐈𝐍_𝐍𝐂𝐂,1,πš…π™°π™»πš„π™΄πš‚.πš•πš–πš’πš—-1)
β€’ πŒπ€π—_ππ‚π‚β‰€πš…π™°π™»πš„π™΄πš‚.πš•πš–πšŠπš‘

Graph model

PartΒ (A) of FigureΒ 5.318.1 shows the initial graphs associated with values 1, 2, 3 and 6 of the Example slot. PartΒ (B) of FigureΒ 5.318.1 shows the corresponding final graphs associated with values 1, 3 and 6. Since value 2 is not assigned to any variable of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection the final graph associated with value 2 is empty. The πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘ constraint holds since:

  • For value 1 we have one connected component for which the number of vertices 3 is greater than or equal to 2 and less than or equal to 4,

  • For value 2 we do not have any connected component,

  • For value 3 we have one connected component for which the number of vertices 1 is greater than or equal to 1 and less than or equal to 6,

  • For value 6 we have two connected components that both contain two vertices: this is greater than or equal to 2 and less than or equal to 2.

Figure 5.318.1. Initial and final graph of the πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘ constraint
ctrs/stretch_pathActrs/stretch_pathB
(a) (b)

During the presentation of this constraint at CP'2001 the following point was mentioned: it could be useful to allow domain variables for the minimum and the maximum values of a stretch. This could be achieved in the following way: the πš•πš–πš’πš— (respectively πš•πš–πšŠπš‘) attribute would now be a domain variable that gives the size of the shortest (respectively longest) stretch. Finally within the Graph property(ies) slot we would replace β‰₯ (and ≀) by =.

Automaton

Let n and m respectively denote the quantities |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| and |πš…π™°π™»πš„π™΄πš‚|. Furthermore, let πšŸπšŠπš• i , πš•πš–πš’πš— i and πš•πš–πšŠπš‘ i , (i∈[1,m]), respectively be shortcuts for the expressions πš…π™°π™»πš„π™΄πš‚[i].πšŸπšŠπš•, πš…π™°π™»πš„π™΄πš‚[i].πš•πš–πš’πš— and πš…π™°π™»πš„π™΄πš‚[i].πš•πš–πšŠπš‘. Without loss of generality, we assume that all the πš•πš–πš’πš— attributes of the items of the πš…π™°π™»πš„π™΄πš‚ collection are at least equal to 1. The following automaton π’œ involving 1+πš•πš–πšŠπš‘ 1 +πš•πš–πšŠπš‘ 2 +...+πš•πš–πšŠπš‘ m states only accepts solutions of the πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘ constraint. Automaton π’œ has the following states:

  • an initial state s that is also a terminal state,

  • βˆ€i∈[1,m],βˆ€j∈[1,πš•πš–πš’πš— i -1], a non -terminal state s i,j ,

  • βˆ€i∈[1,m],βˆ€j∈[πš•πš–πš’πš— i ,πš•πš–πšŠπš‘ i ], a terminal state s i,j .

Transitions of π’œ are defined in the following way:

  • βˆ€i∈[1,m], a transition from s to s i,1 labelled by condition X l =πšŸπšŠπš• i ,

  • a transition from s to s labelled by condition X l β‰ πšŸπšŠπš• 1 ∧X l β‰ πšŸπšŠπš• 2 ∧...∧X l β‰ πšŸπšŠπš• m ,

  • βˆ€i∈[1,m],βˆ€j∈[πš•πš–πš’πš— i ,πš•πš–πšŠπš‘ i ], a transition from s i,j to s labelled by condition X l β‰ πšŸπšŠπš• 1 ∧X l β‰ πšŸπšŠπš• 2 ∧...∧X l β‰ πšŸπšŠπš• m ,

  • βˆ€i∈[1,m],βˆ€j∈[1,πš•πš–πšŠπš‘ i -1], a transition from s i,j to s i,j+1 labelled by condition X l =πšŸπšŠπš• i ,

  • βˆ€i∈[1,m],βˆ€j∈[πš•πš–πš’πš— i ,πš•πš–πšŠπš‘ i ],βˆ€kβ‰ i∈[1,m], a transition from s i,j to s k,1 labelled by condition X l =πšŸπšŠπš• k .

FigureΒ 5.318.2 depicts the automaton associated with the πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘ constraint of the Example slot. Transitions labels 0, 1, 2, 3 and 4 respectively correspond to the conditions X l β‰ 1∧X l β‰ 2∧X l β‰ 3∧X l β‰ 6, X l =1, X l =2, X l =3, X l =6 (since values 1, 2, 3 and 6 respectively correspond to the values of the first, second, third and fourth item of the πš…π™°π™»πš„π™΄πš‚ collection). The πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘ constraint holds since the corresponding sequence of visited states, s s 41 s 42 s 31 s 11 s 12 s 13 s 41 s 42 , ends up in a terminal state (i.e.,Β terminal states are depicted by thick circles in the figure).

Figure 5.318.2. Automaton of the πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘ constraint of the Example slot
ctrs/stretch_path1