5.242. nvector

DESCRIPTIONLINKSGRAPH
Origin

Introduced by G.Β Chabert as a generalisation of πš—πšŸπšŠπš•πšžπšŽ

Constraint

πš—πšŸπšŽπšŒπšπš˜πš›(π™½πš…π™΄π™²,πš…π™΄π™²πšƒπ™Ύπšπš‚)

Type
πš…π™΄π™²πšƒπ™ΎπšπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Arguments
π™½πš…π™΄π™²πšπšŸπšŠπš›
πš…π™΄π™²πšƒπ™Ύπšπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚟𝚎𝚌-πš…π™΄π™²πšƒπ™Ύπš)
Restrictions
π™½πš…π™΄π™²β‰₯πš–πš’πš—(1,|πš…π™΄π™²πšƒπ™Ύπšπš‚|)
π™½πš…π™΄π™²β‰€|πš…π™΄π™²πšƒπ™Ύπšπš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπšπš‚,𝚟𝚎𝚌)
πšœπšŠπš–πšŽ_πšœπš’πš£πšŽ(πš…π™΄π™²πšƒπ™Ύπšπš‚,𝚟𝚎𝚌)
Purpose

π™½πš…π™΄π™² is the number of distinct tuples of values taken by the vectors of the collection πš…π™΄π™²πšƒπ™Ύπšπš‚. Two tuples of values 〈A 1 ,A 2 ,...,A m βŒͺ and 〈B 1 ,B 2 ,...,B m βŒͺ are distinct if and only if there exist an integer i∈[1,m] such that A i β‰ B i .

Example
2,𝚟𝚎𝚌-5,6,𝚟𝚎𝚌-5,6,𝚟𝚎𝚌-9,3,𝚟𝚎𝚌-5,6,𝚟𝚎𝚌-9,3

The πš—πšŸπšŽπšŒπšπš˜πš› constraint holds since its first argument π™½πš…π™΄π™²=2 is set to the number of distinct tuples of values (i.e.,Β tuples 〈5,6βŒͺ and 〈9,3βŒͺ) occurring within the collection πš…π™΄π™²πšƒπ™Ύπšπš‚. FigureΒ 5.242.1 depicts with a thick rectangle a possible initial domain for each of the five vectors and with a grey circle each tuple of values of the corresponding solution.

Figure 5.242.1. Initial possible initial domains (C 11 ∈[1,6], C 12 ∈[2,6], C 21 ∈[3,5], C 22 ∈[6,9], C 31 ∈[4,10], C 32 ∈[1,4], C 41 ∈[5,9], C 42 ∈[3,7], C 51 ∈[9,11], C 52 ∈[0,5]) and solution corresponding to the example
ctrs/nvector1
Symmetries
  • Items of πš…π™΄π™²πšƒπ™Ύπšπš‚ are permutable.

  • Items of πš…π™΄π™²πšƒπ™Ύπšπš‚.𝚟𝚎𝚌 are permutable (same permutation used).

  • All occurrences of two distinct tuples of values of πš…π™΄π™²πšƒπ™Ύπšπš‚.𝚟𝚎𝚌 can be swapped; all occurrences of a tuple of values of πš…π™΄π™²πšƒπ™Ύπšπš‚.𝚟𝚎𝚌 can be renamed to any unused tuple of values.

Remark

It was shown inΒ [ChabertLorca09], [ChabertJaulinLorca09] that, finding out whether a πš—πšŸπšŽπšŒπšπš˜πš› constraint has a solution or not is NP-hard (i.e.,Β the restriction to the rectangle case and to the atmost side of the πš—πšŸπšŽπšŒπšπš˜πš› were considered for this purpose). This was achieved by reduction from the rectangle clique partition problem.

Reformulation

Assume the collection πš…π™΄π™²πšƒπ™Ύπšπš‚ is not empty (otherwise π™½πš…π™΄π™²=0). In this context, let n and m respectively denote the number of vectors of the collection πš…π™΄π™²πšƒπ™Ύπšπš‚ and the number of components of each vector. Furthermore, let Ξ± i =min(C 1i Μ²,C 2i Μ²,...,C ni Μ²), Ξ² i =max(C 1i Β―,C 2i Β―,...,C ni Β―), Ξ³ i =Ξ² i -Ξ± i +1, (i∈[1,m]). By associating to each vector

〈C k1 ,C k2 ,...,C km βŒͺ, (k∈[1,n])

a variable

D k =βˆ‘ 1≀i≀m ∏ i<j≀m Ξ³ j Β·C ki -Ξ± i ,

the constraint

Β Β Β πš—πšŸπšŽπšŒπšπš˜πš›(π™½πš…π™΄π™²,

             〈𝚟𝚎𝚌-〈C 11 ,C 12 ,...,C 1m βŒͺ,

              𝚟𝚎𝚌-〈C 21 ,C 22 ,...,C 2m βŒͺ,

Β Β Β Β Β Β Β Β Β Β Β Β Β Β ........................

              𝚟𝚎𝚌-〈C n1 ,C n2 ,...,C nm βŒͺβŒͺ)

can be expressed in term of the constraint

Β Β Β πš—πšŸπšŠπš•πšžπšŽ(π™½πš…π™΄π™²,〈D 1 ,D 2 ,...,D n βŒͺ).

Note that the previous reformulation does not work anymore if the variables have a continuous domain, or if an overflow occurs while propagating the equality constraint D k =βˆ‘ 1≀i≀m ∏ i<j≀m Ξ³ j Β·C ki -Ξ± i (i.e.,Β the number of components m is too big).

When using this reformulation with respect to the Example slot we first introduce D 1 =1Β·6-3+(4Β·5-20))=3, D 2 =1Β·6-3+(4Β·5-20))=3, D 3 =1Β·3-3+(4Β·9-20))=16, D 4 =1Β·6-3+(4Β·5-20))=3, D 5 =1Β·3-3+(4Β·9-20))=16 and then get the constraint πš—πšŸπšŠπš•πšžπšŽ(2,〈3,3,16,3,16βŒͺ).

See also

common keyword: πš•πšŽπš‘_πšŽπššπšžπšŠπš•, πš˜πš›πšπšŽπš›πšŽπš_πšŠπšπš•πšŽπšŠπšœπš_πš—πšŸπšŽπšŒπšπš˜πš›, πš˜πš›πšπšŽπš›πšŽπš_πšŠπšπš–πš˜πšœπš_πš—πšŸπšŽπšŒπšπš˜πš›Β (vector).

generalisation: πš—πšŸπšŽπšŒπšπš˜πš›πšœΒ (replace an equality with the number of distinct vectors by a comparison with the number of distinct nvectors).

implied by: πš˜πš›πšπšŽπš›πšŽπš_πš—πšŸπšŽπšŒπšπš˜πš›.

specialisation: πšŠπšπš•πšŽπšŠπšœπš_πš—πšŸπšŽπšŒπšπš˜πš›Β (=π™½πš…π™΄π™² replaced by β‰₯π™½πš…π™΄π™²), πšŠπšπš–πš˜πšœπš_πš—πšŸπšŽπšŒπšπš˜πš›Β (=π™½πš…π™΄π™² replaced by β‰€π™½πš…π™΄π™²), πš—πšŸπšŠπš•πšžπšŽΒ (vector replaced by variable).

Keywords

application area: SLAM problem.

characteristic of a constraint: vector.

complexity: rectangle clique partition.

constraint type: counting constraint, value partitioning constraint.

final graph structure: strongly connected component, equivalence.

modelling: number of distinct equivalence classes.

problems: domination.

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.242.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 tuple of values that is assigned to some vectors of the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection. The 2 following tuple of values 〈5,6βŒͺ and 〈9,3βŒͺ are used by the vectors of the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection.

Figure 5.242.2. Initial and final graph of the πš—πšŸπšŽπšŒπšπš˜πš› constraint
ctrs/nvectorActrs/nvectorB
(a) (b)