Global Constraint Catalog: Cnvectors

5.291. nvectors

DESCRIPTION

LINKS

GRAPH

Origin

Inspired by $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ and $𝚌𝚘𝚞𝚗𝚝$ .

Constraint

$𝚗𝚟𝚎𝚌𝚝𝚘𝚛𝚜 (𝚅𝙴𝙲𝚃𝙾𝚁𝚂, 𝚁𝙴𝙻𝙾𝙿, 𝙻𝙸𝙼𝙸𝚃)$

Synonym

$𝚗𝚙𝚘𝚒𝚗𝚝𝚜$ .

Type

𝚅𝙴𝙲𝚃𝙾𝚁

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

Arguments

$𝚅𝙴𝙲𝚃𝙾𝚁𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚎𝚌 - 𝚅𝙴𝙲𝚃𝙾𝚁)$
$𝚁𝙴𝙻𝙾𝙿$	$𝚊𝚝𝚘𝚖$
$𝙻𝙸𝙼𝙸𝚃$	$𝚍𝚟𝚊𝚛$

Restrictions

| 𝚅𝙴𝙲𝚃𝙾𝚁 | \geq 1

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚜𝚊𝚖𝚎_𝚜𝚒𝚣𝚎

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

𝚁𝙴𝙻𝙾𝙿 \in [=, \neq, <, \geq, >, \leq]

Purpose

Let $N$ be the number of distinct tuples of values taken by the vectors of the $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ collection. Enforce condition $N 𝚁𝙴𝙻𝙾𝙿 𝙻𝙸𝙼𝙸𝚃$ to hold.

Example

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

The $𝚗𝚟𝚎𝚌𝚝𝚘𝚛𝚜$ constraint holds since the number of distinct tuples of values (i.e., tuples $〈 5, 6 〉$ and $〈 9, 3 〉$ ) occurring within the collection $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ is equal (i.e., $𝚁𝙴𝙻𝙾𝙿$ is set to $=$ ) to its third argument $𝙻𝙸𝙼𝙸𝚃 = 2$ .

Typical

| 𝚅𝙴𝙲𝚃𝙾𝚁 | > 1

| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | > 1

𝚁𝙴𝙻𝙾𝙿 \in [=, <, \geq, >, \leq]

𝙻𝙸𝙼𝙸𝚃 > 1

𝙻𝙸𝙼𝙸𝚃 < | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 |

Symmetries

Items of $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ are permutable.
Items of $𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌$ are permutable (same permutation used).
All occurrences of two distinct values of $𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌$ can be swapped; all occurrences of a value of $𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌$ can be renamed to any unused value.

Arg. properties

Contractible wrt. $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ when $𝚁𝙴𝙻𝙾𝙿 \in [<, \leq]$ .
Extensible wrt. $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ when $𝚁𝙴𝙻𝙾𝙿 \in [\geq, >]$ .

Reformulation

The $𝚗𝚟𝚎𝚌𝚝𝚘𝚛𝚜$ $(𝚅𝙴𝙲𝚃𝙾𝚁𝚂, 𝚁𝙴𝙻𝙾𝙿, 𝙻𝙸𝙼𝙸𝚃)$ constraint can be expressed in term of the conjunction $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ $(𝑁𝑉, 𝚅𝙴𝙲𝚃𝙾𝚁𝚂)$ $\land$ $𝑁𝑉 𝚁𝙴𝙻𝙾𝙿 𝙻𝙸𝙼𝙸𝚃$ .

See also

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

Keywords

characteristic of a constraint: vector.

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

𝐶𝐿𝐼𝑄𝑈𝐸

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

Arc arity

Arc constraint(s)

𝚕𝚎𝚡_𝚎𝚚𝚞𝚊𝚕

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

Graph property(ies)

𝐍𝐒𝐂𝐂

𝚁𝙴𝙻𝙾𝙿 𝙻𝙸𝙼𝙸𝚃

Graph class

𝙴𝚀𝚄𝙸𝚅𝙰𝙻𝙴𝙽𝙲𝙴

Graph model

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


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.291. nvectors

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

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