5.161. increasing_nvalue

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Conjoin πš—πšŸπšŠπš•πšžπšŽ and πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš.

Constraint

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

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

The variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are increasing. In addition, π™½πš…π™°π™» is the number of distinct values taken by the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Example
(2,6,6,8,8,8)

The πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽ constraint (see FigureΒ 5.161.1 for a graphical representation) holds since:

  • The values of the collection 〈6,6,8,8,8βŒͺ are sorted in increasing order.

  • π™½πš…π™°π™»=2 is set to the number of distinct values occurring within the collection 〈6,6,8,8,8βŒͺ.

Figure 5.161.1. The solution associated with the example
ctrs/increasing_nvalue1
Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
Symmetry

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

Algorithm

A complete filtering algorithm in a linear time complexity over the sum of the domain sizes is described inΒ [BeldiceanuHermenierLorcaPetit10]. A generalisation of this algorithm to other constraints is given inΒ [BeldiceanuLorcaPetit10].

Reformulation

The πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽ constraint can be expressed in term of a conjunction of a πš—πšŸπšŠπš•πšžπšŽ and an πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš constraints (i.e.,Β a chain of non strict inequality constraints on adjacent variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚). But as shown by the following example, V 1 ∈[1,2], V 2 ∈[1,2], V 1 ≀V 2 , πš—πšŸπšŠπš•πšžπšŽ(2,〈V 1 ,V 2 βŒͺ), this hinders propagation (i.e.,Β the unique solution V 1 =1, V 2 =2 is not directly obtained after stating all the previous constraints).

Systems

increasingNValue in Choco.

See also

implies: πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πšΒ (remove π™½πš…π™°π™» parameter from πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽ), πš—πšŸπšŠπš•πšžπšŽ.

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

shift of concept: πš˜πš›πšπšŽπš›πšŽπš_πš—πšŸπšŽπšŒπšπš˜πš›Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŸπšŽπšŒπšπš˜πš› and ≀ replaced by πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš).

Keywords

constraint type: counting constraint, value partitioning constraint, order constraint.

final graph structure: strongly connected component, equivalence.

modelling: number of distinct equivalence classes, number of distinct values.

symmetry: symmetry.

Arc input(s)

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

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
𝐍𝐒𝐂𝐂=π™½πš…π™°π™»

Graph class
π™΄πš€πš„π™Έπš…π™°π™»π™΄π™½π™²π™΄

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.161.2 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐒𝐂𝐂 graph property we show the different strongly connected components of the final graph. Each strongly connected component corresponds to a value that is assigned to some variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. The 2 following values 6 and 8 are used by the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection.

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

A first systematic approach for creating an automaton that only recognises the solutions of the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽ constraint could be to:

However this approach is not going to scale well in practice since the automaton associated with the πš—πšŸπšŠπš•πšžπšŽ constraint has a too big size. Therefore we propose an approach where we directly construct in one single step the automaton that only recognises the solutions of the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽ constraint. Note that we do not have any formal proof that the resulting automaton is always minimum.

Without loss of generality, assume that the collection of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ 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 variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚, the smallest value that can be assigned to the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚, and the largest value that can be assigned to the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. Let s=π‘šπ‘Žπ‘₯-π‘šπ‘–π‘›+1 denote the total number of potential values. Clearly, the maximum number of distinct values that can be assigned to the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ cannot exceed the quantity d=min(m,n,s). The sΒ·(s+1) 2-(s-d)Β·(s-d+1) 2+1 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 sΒ·(s+1) 2-(s-d)Β·(s-d+1) 2 states labelled by s ij (1≀i≀d,i≀j≀s). The first index i of a state s ij corresponds to the number of distinct values already encountered, while the second index j denotes the the current value (i.e.,Β more precisely the index of the current value, where the minimum value has index 1).

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 π™½πš…π™°π™»). Three classes of transitions are respectively defined in the following way:

  1. There is a transition, labelled by π‘šπ‘–π‘›+j-1, from the initial state s 00 to the state s 1j (1≀j≀s).

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

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

We respectively have s transitions of class 1, sΒ·(s+1) 2-(s-d)Β·(s-d+1) 2 transitions of class 2, and (s-1)Β·sΒ·(s+1) 6-(s-d)Β·(s-d+1)Β·(s-d+2) 6 transitions of class 3.

Note that all states s ij such that i+s-j<l can be discarded since they do not allow to reach the minimum number of distinct values required l.

PartΒ (A) of FigureΒ 5.161.3 depicts the automaton associated with the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽ constraint of the Example slot. For this purpose, we assume that variable π™½πš…π™°π™» is fixed to value 2 and that variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ take their values within interval [6,8]. PartΒ (B) of FigureΒ 5.161.3 represents the simplified automaton where all states that do not allow to reach a terminal state were removed. The πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint holds since the corresponding sequence of visited states, s 00 s 11 s 11 s 23 s 23 s 23 , ends up in a terminal state (i.e.,Β terminal states are depicted by thick circles in the figure).

Figure 5.161.3. Automaton – PartΒ A – and simplified automaton – PartΒ B – of the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽ constraint of the Example slot: the path corresponding to the solution 〈6,6,8,8,8βŒͺ is depicted by thick arcs
ctrs/increasing_nvalue2