Global Constraint Catalog: Cnvector

5.290. nvector

DESCRIPTION

LINKS

GRAPH

Origin

Introduced by G. Chabert as a generalisation of $𝚗𝚟𝚊𝚕𝚞𝚎$

Constraint

$𝚗𝚟𝚎𝚌𝚝𝚘𝚛 (𝙽𝚅𝙴𝙲, 𝚅𝙴𝙲𝚃𝙾𝚁𝚂)$

Synonyms

$𝚗𝚟𝚎𝚌𝚝𝚘𝚛𝚜$ , $𝚗𝚙𝚘𝚒𝚗𝚝$ , $𝚗𝚙𝚘𝚒𝚗𝚝𝚜$ .

Type

𝚅𝙴𝙲𝚃𝙾𝚁

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)

Arguments

$𝙽𝚅𝙴𝙲$	$𝚍𝚟𝚊𝚛$
$𝚅𝙴𝙲𝚃𝙾𝚁𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚎𝚌 - 𝚅𝙴𝙲𝚃𝙾𝚁)$

Restrictions

| 𝚅𝙴𝙲𝚃𝙾𝚁 | \geq 1

𝙽𝚅𝙴𝙲 \geq 𝚖𝚒𝚗 (1, | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 |)

𝙽𝚅𝙴𝙲 \leq | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙴𝙲𝚃𝙾𝚁𝚂, 𝚟𝚎𝚌)

𝚜𝚊𝚖𝚎_𝚜𝚒𝚣𝚎

(𝚅𝙴𝙲𝚃𝙾𝚁𝚂, 𝚟𝚎𝚌)

Purpose

$𝙽𝚅𝙴𝙲$ is the number of distinct tuples of values taken by the vectors of the collection $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ . Two tuples of values $〈 A_{1}, A_{2}, \dots, A_{m} 〉$ and $〈 B_{1}, B_{2}, \dots, B_{m} 〉$ are $d i s t i n c t$ if and only if there exist an integer $i \in [1, m]$ such that $A_{i} \neq B_{i}$ .

Example

(\begin{matrix} 2, 〈\begin{matrix} 𝚟𝚎𝚌 - 〈5, 6〉, \\ 𝚟𝚎𝚌 - 〈5, 6〉, \\ 𝚟𝚎𝚌 - 〈9, 3〉, \\ 𝚟𝚎𝚌 - 〈5, 6〉, \\ 𝚟𝚎𝚌 - 〈9, 3〉 \end{matrix}〉 \end{matrix})

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.290.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.290.1. Possible initial domains ( $C_{11} \in [1, 6]$ , $C_{12} \in [2, 6]$ , $C_{21} \in [3, 5]$ , $C_{22} \in [6, 9]$ , $C_{31} \in [4, 10]$ , $C_{32} \in [1, 4]$ , $C_{41} \in [5, 9]$ , $C_{42} \in [3, 7]$ , $C_{51} \in [9, 11]$ , $C_{52} \in [0, 5]$ ) and solution corresponding to the Example slot: we have two distinct vectors ( $𝙽𝚅𝙴𝙲 = 2$ )

Typical

| 𝚅𝙴𝙲𝚃𝙾𝚁 | > 1

𝙽𝚅𝙴𝙲 > 1

𝙽𝚅𝙴𝙲 < | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 |

| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | > 1

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.

Arg. properties

Functional dependency: $𝙽𝚅𝙴𝙲$ determined by $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ .
Contractible wrt. $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ when $𝙽𝚅𝙴𝙲 = 1$ and $| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | > 0$ .
Contractible wrt. $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ when $𝙽𝚅𝙴𝙲 = | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 |$ .

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 (\underset{̲}{C_{1 i}}, \underset{̲}{C_{2 i}}, \dots, \underset{̲}{C_{n i}})$ , $β_{i} = max (\bar{C_{1 i}}, \bar{C_{2 i}}, \dots, \bar{C_{n i}})$ , $γ_{i} = β_{i} - α_{i} + 1$ , $(i \in [1, m])$ . By associating to each vector

〈 C_{k 1}, C_{k 2}, \dots, C_{k m} 〉, (k \in [1, n])

a variable

D_{k} = \sum_{1 \leq i \leq m} ((\prod_{i < j \leq m} γ_{j}) \cdot (C_{k i} - α_{i})),

the constraint

$𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ $(𝙽𝚅𝙴𝙲,$

$〈 𝚟𝚎𝚌 - 〈 C_{11}, C_{12}, \dots, C_{1 m} 〉,$

$𝚟𝚎𝚌 - 〈 C_{21}, C_{22}, \dots, C_{2 m} 〉,$

$\dots \dots \dots \dots \dots \dots \dots \dots$

$𝚟𝚎𝚌 - 〈 C_{n 1}, C_{n 2}, \dots, C_{n m} 〉 〉)$

can be expressed in term of the constraint

$𝚗𝚟𝚊𝚕𝚞𝚎$ $(𝙽𝚅𝙴𝙲, 〈 D_{1}, D_{2}, \dots, 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} = \sum_{1 \leq i \leq m} ((\prod_{i < j \leq m} γ_{j}) \cdot (C_{k i} - α_{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 \cdot 6 - 3 + (4 \cdot 5 - 20)) = 3$ , $D_{2} = 1 \cdot 6 - 3 + (4 \cdot 5 - 20)) = 3$ , $D_{3} = 1 \cdot 3 - 3 + (4 \cdot 9 - 20)) = 16$ , $D_{4} = 1 \cdot 6 - 3 + (4 \cdot 5 - 20)) = 3$ , $D_{5} = 1 \cdot 3 - 3 + (4 \cdot 9 - 20)) = 16$ and then get the constraint $𝚗𝚟𝚊𝚕𝚞𝚎$ $(2, 〈 3, 3, 16, 3, 16 〉)$ .

generalisation: $𝚗𝚟𝚎𝚌𝚝𝚘𝚛𝚜$ (replace an equality with the number of distinct vectors by a comparison with the number of distinct nvectors).

implied by: $𝚘𝚛𝚍𝚎𝚛𝚎𝚍_𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ .

implies: $𝚊𝚝𝚕𝚎𝚊𝚜𝚝_𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ ( $= 𝙽𝚅𝙴𝙲$ replaced by $\geq 𝙽𝚅𝙴𝙲$ ), $𝚊𝚝𝚖𝚘𝚜𝚝_𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ ( $= 𝙽𝚅𝙴𝙲$ replaced by $\leq 𝙽𝚅𝙴𝙲$ ).

specialisation: $𝚗𝚟𝚊𝚕𝚞𝚎$ (vector replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ ).

Keywords

application area: SLAM problem.

characteristic of a constraint: vector.

complexity: rectangle clique partition.

constraint arguments: pure functional dependency.

constraint type: counting constraint, value partitioning constraint.

final graph structure: strongly connected component, equivalence.

modelling: number of distinct equivalence classes, functional dependency.

problems: domination.

Arc input(s)

$𝚅𝙴𝙲𝚃𝙾𝚁𝚂$

Arc generator

𝐶𝐿𝐼𝑄𝑈𝐸

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚎𝚌𝚝𝚘𝚛𝚜 1, 𝚟𝚎𝚌𝚝𝚘𝚛𝚜 2)

Arc arity

Arc constraint(s)

𝚕𝚎𝚡_𝚎𝚚𝚞𝚊𝚕

(𝚟𝚎𝚌𝚝𝚘𝚛𝚜 1 . 𝚟𝚎𝚌, 𝚟𝚎𝚌𝚝𝚘𝚛𝚜 2 . 𝚟𝚎𝚌)

Graph property(ies)

𝐍𝐒𝐂𝐂

= 𝙽𝚅𝙴𝙲

Graph class

𝙴𝚀𝚄𝙸𝚅𝙰𝙻𝙴𝙽𝙲𝙴

Graph model

Parts (A) and (B) of Figure 5.290.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.290.2. Initial and final graph of the $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ constraint


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.290. nvector

Figure 5.290.1. 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 slot: we have two distinct vectors (𝙽𝚅𝙴𝙲=2)

Figure 5.290.2. Initial and final graph of the 𝚗𝚟𝚎𝚌𝚝𝚘𝚛 constraint

Figure 5.290.2. Initial and final graph of the $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ constraint