5.317. stretch_circuit

DESCRIPTIONLINKSGRAPH
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 πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ and let i, j (0≀i<n,0≀j<n) be two positions within the collection of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ such that the following conditions apply:

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

    If i>j then all variables X i ,...,X n-1 ,X 0 ,...,X j take a same value from the set of values of the πšŸπšŠπš• attribute.

  • X (i-1) mod n is different from X i .

  • X (j+1) mod n is different from X j .

We call such a set of variables a stretch. The span of the stretch is equal to 1+(j-i) mod n, 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.

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πš•πš–πšŠπš‘-4

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

  • The span of the first stretch 6 6 6 6 is located within interval [2,4] (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).

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

  • 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 origin πšœπšπš›πšŽπšπšŒπš‘ constraint into the πšœπšπš›πšŽπšπšŒπš‘_πšŒπš’πš›πšŒπšžπš’πš and the πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘ constraints that respectively use the 𝑃𝐴𝑇𝐻 𝐿𝑂𝑂𝑃 and πΆπΌπ‘…πΆπ‘ˆπΌπ‘‡ 𝐿𝑂𝑂𝑃 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.

Algorithm

A first filtering algorithm was described in the original article of G.Β PesantΒ [Pesant01]. An algorithm that also generates explanations is given inΒ [RochartJussien03]. The first filtering algorithm achieving arc-consistency is depicted inΒ [Hellsten04], [HellstenPesantBeek04]. This algorithm is based on dynamic programming and handles the fact that some values can be followed by only a given subset of values.

Reformulation

The πšœπšπš›πšŽπšπšŒπš‘_πšŒπš’πš›πšŒπšžπš’πš constraint can be reformulated in term of a πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘ constraint. Let 𝐿𝑀𝐴𝑋 denote the maximum value taken by the πš•πš–πšŠπš‘ attribute within the items of the collection πš…π™°π™»πš„π™΄πš‚, let n be the number of variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚, and let Ξ΄=min(𝐿𝑀𝐴𝑋,n). The first and second arguments of the πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘ constraint are created in the following way:

Even if πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘ can achieve arc-consistency this reformulation may not achieve arc-consistency since it duplicates variables.

Using this reformulation, the example

Β Β Β πšœπšπš›πšŽπšπšŒπš‘_πšŒπš’πš›πšŒπšžπš’πš(〈6,6,3,1,1,1,6,6βŒͺ,

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β βŒ©πšŸπšŠπš•-1 πš•πš–πš’πš—-2 πš•πš–πšŠπš‘-4, πšŸπšŠπš•-2 πš•πš–πš’πš—-2 πš•πš–πšŠπš‘-3,

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β πšŸπšŠπš•-3 πš•πš–πš’πš—-1 πš•πš–πšŠπš‘-6, πšŸπšŠπš•-6 πš•πš–πš’πš—-2 πš•πš–πšŠπš‘-4βŒͺ)

of the Example slot is reformulated as:

Β Β Β πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘(〈6,6,3,1,1,1,6,6,6,6,3,1,1,1βŒͺ,

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β βŒ©πšŸπšŠπš•-1 πš•πš–πš’πš—-2 πš•πš–πšŠπš‘-4, πšŸπšŠπš•-2 πš•πš–πš’πš—-2 πš•πš–πšŠπš‘-3,

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β πšŸπšŠπš•-3 πš•πš–πš’πš—-1 πš•πš–πšŠπš‘-6, πšŸπšŠπš•-6 πš•πš–πš’πš—-2 πš•πš–πšŠπš‘-4βŒͺ)

In the reformulation Ξ΄ was equal to 6, and the πš…π™°π™»πš„π™΄πš‚ collection was left unchanged since no πš•πš–πšŠπš‘ attribute was equal to the number of variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection (i.e.,Β 8).

See also

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

πš™πšŠπšπšπšŽπš›πš—Β (sliding sequence constraint,timetabling constraint),

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

used in reformulation: πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘.

Keywords

characteristic of a constraint: cyclic.

constraint type: timetabling constraint, sliding sequence constraint.

filtering: dynamic programming, arc-consistency, duplicated variables.

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.317.1 shows the initial graphs associated with values 1, 2, 3 and 6 of the Example slot. PartΒ (B) of FigureΒ 5.317.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 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 is greater than or equal to 1 and less than or equal to 6,

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

Figure 5.317.1. Initial and final graph of the πšœπšπš›πšŽπšπšŒπš‘_πšŒπš’πš›πšŒπšžπš’πš constraint
ctrs/stretch_circuitActrs/stretch_circuitB
(a) (b)