5.298. smooth

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from πšŒπš‘πšŠπš—πšπšŽ.

Constraint

πšœπš–πš˜πš˜πšπš‘(𝙽𝙲𝙷𝙰𝙽𝙢𝙴,πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Arguments
π™½π™²π™·π™°π™½π™Άπ™΄πšπšŸπšŠπš›
πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄πš’πš—πš
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
𝙽𝙲𝙷𝙰𝙽𝙢𝙴β‰₯0
𝙽𝙲𝙷𝙰𝙽𝙢𝙴<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄β‰₯0
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

𝙽𝙲𝙷𝙰𝙽𝙢𝙴 is the number of times that |X-Y|>πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄ holds; X and Y correspond to consecutive variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Example
(1,2,1,3,4,5,2)

In the example we have one change between values 5 and 2 since the difference in absolute value is greater than the tolerance (i.e.,Β |5-2|>2). Consequently the 𝙽𝙲𝙷𝙰𝙽𝙢𝙴 argument is fixed to 1 and the πšœπš–πš˜πš˜πšπš‘ constraint holds.

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

  • One and the same constant can be added to the πšŸπšŠπš› attribute of all items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Usage

This constraint is useful for the following problems:

  • Assume that πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds to the number of people that work on consecutive weeks. One may not normally increase or decrease too drastically the number of people from one week to the next week. With the πšœπš–πš˜πš˜πšπš‘ constraint you can state a limit on the number of drastic changes.

  • Assume you have to produce a set of orders, each order having a specific attribute. You want to generate the orders in such a way that there is not a too big difference between the values of the attributes of two consecutive orders. If you can't achieve this on two given specific orders, this would imply a set-up or a cost. Again, with the πšœπš–πš˜πš˜πšπš‘ constraint, you can control this kind of drastic changes.

Algorithm

A first incomplete algorithm is described inΒ [BeldiceanuCarlsson01]. The sketch of a filtering algorithm for the conjunction of the πšœπš–πš˜πš˜πšπš‘ and the πšœπšπš›πšŽπšπšŒπš‘ constraints based on dynamic programming achieving arc -consistency is mentioned by LarsΒ Hellsten inΒ [Hellsten04]. An arc -consistency algorithm in linear time of the sum of domain sizes is described inΒ [BeldiceanuLorcaPetit10].

See also

common keyword: πšŒπš‘πšŠπš—πšπšŽΒ (number of changes in a sequence with respect to a binary constraint).

related: πšπš’πšœπšπšŠπš—πšŒπšŽ.

Keywords

characteristic of a constraint: automaton, automaton with counters, non-deterministic automaton, non-deterministic automaton.

constraint network structure: sliding cyclic(1) constraint network(2), Berge-acyclic constraint network.

constraint type: timetabling constraint.

filtering: dynamic programming, arc-consistency.

modelling: number of changes.

modelling exercises: n-Amazon.

puzzles: n-Amazon.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πšŠπš‹πšœ(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›-πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›)>πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄
Graph property(ies)
𝐍𝐀𝐑𝐂=𝙽𝙲𝙷𝙰𝙽𝙢𝙴

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.298.1 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property, the unique arc of the final graph is stressed in bold.

Figure 5.298.1. Initial and final graph of the πšœπš–πš˜πš˜πšπš‘ constraint
ctrs/smoothActrs/smoothB
(a) (b)
Automaton

FigureΒ 5.298.2 depicts a first automaton that only accepts all the solutions of the πšœπš–πš˜πš˜πšπš‘ constraint. This automaton uses a counter in order to record the number of satisfied constraints of the form (|πš…π™°πš i -πš…π™°πš i+1 |)>πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄ already encountered. To each pair of consecutive variables (πš…π™°πš i ,πš…π™°πš i+1 ) of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a 0-1 signature variable πš‚ i . The following signature constraint links πš…π™°πš i , πš…π™°πš i+1 and πš‚ i : (|πš…π™°πš i -πš…π™°πš i+1 |)>πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄β‡”πš‚ i =1.

Figure 5.298.2. Automaton (with a counter) of the πšœπš–πš˜πš˜πšπš‘ constraint
ctrs/smooth1
Figure 5.298.3. Hypergraph of the reformulation corresponding to the automaton (with a counter) of the πšœπš–πš˜πš˜πšπš‘ constraint
ctrs/smooth2

Since the reformulation associated with the previous automaton is not Berge-acyclic, we now describe a second counter free automaton that also only accepts all the solutions of the πšœπš–πš˜πš˜πšπš‘ constraint. Without loss of generality, assume that the collection of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ contains at least two variables (i.e.,Β |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|β‰₯2). Let n, π‘šπ‘–π‘›, π‘šπ‘Žπ‘₯, and π’Ÿ respectively denote the number of variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚, the smallest value that can be assigned to the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚, the largest value that can be assigned to the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚, and the union of the domains of the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. Clearly, the maximum number of changes (i.e.,Β the number of times the constraint (|πš…π™°πš i -πš…π™°πš i+1 |)>πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄ (1≀i<n) holds) cannot exceed the quantity m=min(n-1,𝙽𝙲𝙷𝙰𝙽𝙢𝙴 Β―). The (m+1)Β·|π’Ÿ|+2 states of the automaton that only accepts all the solutions of the πšœπš–πš˜πš˜πšπš‘ constraint are defined in the following way:

  • We have an initial state labelled by s I .

  • We have mΒ·|π’Ÿ| intermediate states labelled by s ij (iβˆˆπ’Ÿ,j∈[0,m]). The first subscript i of state s ij corresponds to the value currently encountered. The second subscript j denotes the number of already encountered satisfied constraints of the form (|πš…π™°πš k -πš…π™°πš k+1 |)>πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄ from the initial state s I to the state s ij .

  • We have a final state labelled by s F .

Four classes of transitions are respectively defined in the following way:

  1. There is a transition, labelled by i from the initial state s I to the state s i0 , (iβˆˆπ’Ÿ).

  2. There is a transition, labelled by j, from every state s ij , (iβˆˆπ’Ÿ,j∈[0,m]), to the final state s F .

  3. βˆ€iβˆˆπ’Ÿ, βˆ€j∈[0,m], βˆ€kβˆˆπ’Ÿβˆ©[max(π‘šπ‘–π‘›,i-πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄),min(π‘šπ‘Žπ‘₯,i+πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄)] there is a transition labelled by k from s ij to s kj (i.e.,Β the counter j does not change for values k that are too closed from value i).

  4. βˆ€iβˆˆπ’Ÿ, βˆ€j∈[0,m-1], βˆ€kβˆˆπ’Ÿβˆ–[max(π‘šπ‘–π‘›,i-πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄),min(π‘šπ‘Žπ‘₯,i+πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄)] there is a transition labelled by k from s ij to s kj+1 (i.e.,Β the counter j is incremented by +1 for values k that are too far from i).

We have |π’Ÿ| transitions of typeΒ 1, |π’Ÿ|Β·(m+1) transitions of typeΒ 2, and at least |π’Ÿ| 2 Β·m transitions of typesΒ 3 and 4. Since the maximum value of m is equal to n-1, in the worst case we have at least |π’Ÿ| 2 Β·(n-1) transitions. This leads to a worst case time complexity of O(|π’Ÿ| 2 Β·n 2 ) if we use Pesant's algorithm for filtering the πš›πšŽπšπšžπš•πšŠπš› constraintΒ [Pesant04].

FigureΒ 5.298.4 depicts the corresponding counter free non deterministic automaton associated with the πšœπš–πš˜πš˜πšπš‘ constraint under the hypothesis that (1)Β all variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are assigned a value in {0,1,2,3}, (2)Β |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| is equal to 4, and (3)Β πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄ is equal to 1.

Figure 5.298.4. Counter free non deterministic automaton of the πšœπš–πš˜πš˜πšπš‘(𝙽𝙲𝙷𝙰𝙽𝙢𝙴,1,βŒ©πš…π™°πš 1 ,πš…π™°πš 2 ,πš…π™°πš 3 ,πš…π™°πš 4 βŒͺ) constraint assuming πš…π™°πš i ∈[0,3] (1≀i≀3), with initial state s I and final state s F
ctrs/smooth3