5.162. increasing_nvalue_chain

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽ.

Constraint

πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽ_πšŒπš‘πšŠπš’πš—(π™½πš…π™°π™»,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

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

For each consecutive pair of items πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i],πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i+1] (1≀i<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|) of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection at least one of the following conditions hold:

  1. πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i+1].πš‹=0,

  2. πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i].πšŸπšŠπš›β‰€πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i+1].πšŸπšŠπš›.

In addition, π™½πš…π™°π™» is equal to number of pairs of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i],πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i+1] (1≀i<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|) plus one, which verify at least one of the following conditions:

  1. πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i+1].πš‹=0,

  2. πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i].πšŸπšŠπš›<πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i+1].πšŸπšŠπš›.

Note that πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[1].πš‹ is not referenced at all in the previous definition (i.e.,Β its value does not influence at all the values assigned to the other variables).

Example
6,πš‹-0πšŸπšŠπš›-2,πš‹-1πšŸπšŠπš›-4,πš‹-1πšŸπšŠπš›-4,πš‹-1πšŸπšŠπš›-4,πš‹-0πšŸπšŠπš›-4,πš‹-1πšŸπšŠπš›-8,πš‹-0πšŸπšŠπš›-1,πš‹-0πšŸπšŠπš›-7,πš‹-1πšŸπšŠπš›-7

The πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽ_πšŒπš‘πšŠπš’πš— constraint holds since:

  1. The condition πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i+1].πš‹=0βˆ¨πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i].πšŸπšŠπš›β‰€πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i+1].πšŸπšŠπš› holds for every pair of adjacent items of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection:

    • For the pair (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[1].πšŸπšŠπš›,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[2].πšŸπšŠπš›) we have πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[1].πšŸπšŠπš›β‰€πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[2].πšŸπšŠπš› (2≀4).

    • For the pair (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[2].πšŸπšŠπš›,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[3].πšŸπšŠπš›) we have πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[2].πšŸπšŠπš›β‰€πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[3].πšŸπšŠπš› (4≀4).

    • For the pair (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[3].πšŸπšŠπš›,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[4].πšŸπšŠπš›) we have πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[3].πšŸπšŠπš›β‰€πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[4].πšŸπšŠπš› (4≀4).

    • For the pair (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[4].πšŸπšŠπš›,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[5].πšŸπšŠπš›) we have πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[5].πš‹=0.

    • For the pair (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[5].πšŸπšŠπš›,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[6].πšŸπšŠπš›) we have πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[5].πšŸπšŠπš›β‰€πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[6].πšŸπšŠπš› (4≀8).

    • For the pair (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[6].πšŸπšŠπš›,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[7].πšŸπšŠπš›) we have πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[7].πš‹=0.

    • For the pair (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[7].πšŸπšŠπš›,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[8].πšŸπšŠπš›) we have πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[8].πš‹=0.

    • For the pair (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[8].πšŸπšŠπš›,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[9].πšŸπšŠπš›) we have πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[8].πšŸπšŠπš›β‰€πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[9].πšŸπšŠπš› (7≀7).

  2. π™½πš…π™°π™» is equal to number of pairs of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i],πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i+1] (1≀i<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|) plus one which verify at least πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i+1].πš‹=0βˆ¨πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i].πšŸπšŠπš›<πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i+1].πšŸπšŠπš›. Beside the plus one, the following five pairs contribute for 1 in π™½πš…π™°π™»:

    • For the pair (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[1].πšŸπšŠπš›,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[2].πšŸπšŠπš›) we have πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[1].πšŸπšŠπš›β‰€πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[2].πšŸπšŠπš› (2<4).

    • For the pair (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[4].πšŸπšŠπš›,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[5].πšŸπšŠπš›) we have πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[5].πš‹=0.

    • For the pair (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[5].πšŸπšŠπš›,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[6].πšŸπšŠπš›) we have πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[5].πšŸπšŠπš›β‰€πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[6].πšŸπšŠπš› (4<8).

    • For the pair (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[6].πšŸπšŠπš›,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[7].πšŸπšŠπš›) we have πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[7].πš‹=0.

    • For the pair (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[7].πšŸπšŠπš›,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[8].πšŸπšŠπš›) we have πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[8].πš‹=0.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πš‹)>1
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
See also

related: πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽ, πš—πšŸπšŠπš•πšžπšŽ, πš˜πš›πšπšŽπš›πšŽπš_πš—πšŸπšŽπšŒπšπš˜πš›.

Keywords

constraint type: counting constraint, order constraint.

modelling: number of distinct values.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πš‹=0βˆ¨πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›β‰€πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-1

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πš‹=0βˆ¨πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›<πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
𝐍𝐀𝐑𝐂=π™½πš…π™°π™»-1

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.162.1 respectively show the initial and final graph associated with the second graph constraint of the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property the arcs of the final graph are stressed in bold.

Figure 5.162.1. Initial and final graph of the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽ_πšŒπš‘πšŠπš’πš— constraint
ctrs/increasing_nvalue_chainActrs/increasing_nvalue_chainB
(a) (b)
Automaton

Without loss of generality, assume that the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ contains at least one variable (i.e.,Β |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|β‰₯1). Let l, m, n, π‘šπ‘–π‘› and π‘šπ‘Žπ‘₯ respectively denote the minimum and maximum possible value of variable π™½πš…π™°π™», the number of items of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚, the smallest value that can be assigned to πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i].πšŸπšŠπš› (1≀i≀n), and the largest value that can be assigned to πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i].πšŸπšŠπš› (1≀i≀n). Let s=π‘šπ‘Žπ‘₯-π‘šπ‘–π‘›+1 denote the total number of potential values. Clearly, the maximum value of π™½πš…π™°π™» cannot exceed the quantity d=min(m,n). The states of the automaton that only accepts solutions of the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽ_πšŒπš‘πšŠπš’πš— constraint can be defined in the following way:

  • We have an initial state labelled by s 00 .

  • We have dΒ·s states labelled by s ij (1≀i≀d,1≀j≀s).

Terminal states depend on the possible values of variable π™½πš…π™°π™» and correspond to those states s ij such that i is a possible value for variable π™½πš…π™°π™». Note that we assume no further restriction on the domain of π™½πš…π™°π™» (otherwise the set of terminal states needs to be reduced in order to reflect the current set of possible values of π™½πš…π™°π™»).

Transitions of the automaton are labelled by a pair of values (Ξ±,Ξ²) and correspond to a condition of the form πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i].πš‹=Ξ±βˆ§πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i].πšŸπšŠπš›=Ξ², (1≀i≀n). Characters * and + respectively represent all values in {0,1} and all values in {π‘šπ‘–π‘›,π‘šπ‘–π‘›+1,...,π‘šπ‘Žπ‘₯}. Four classes of transitions are respectively defined in the following way:

  1. There is a transition, labelled by the pair (*,π‘šπ‘–π‘›+j-1), from the initial state s 00 to the state s 1j (1≀j≀s). We use the * character since πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[1].πš‹ is not use at all in the definition of the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽ_πšŒπš‘πšŠπš’πš— constraint.

  2. There is a loop, labelled by the pair (1,π‘šπ‘–π‘›+j-1) for every state s ij (1≀i≀d,1≀j≀s).

  3. βˆ€i∈[1,d-1],βˆ€j∈[1,s],βˆ€k∈[j+1,s] there is a transition labelled by the pair (1,π‘šπ‘–π‘›+k-1) from s ij to s i+1k .

  4. βˆ€i∈[1,d-1],βˆ€j∈[1,s] there is a transition labelled by the pair (0,+) from s ij to s i+1 1 .

Figure 5.162.2. Automaton of the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽ_πšŒπš‘πšŠπš’πš— constraint under the hypothesis that all variables are assigned a value in {6,7,8} and that π™½πš…π™°π™» is equal to 2. The character * on a transition corresponds to a 0 or to a 1 and the + corresponds to a 6, 7 or 8.
ctrs/increasing_nvalue_chain1