Global Constraint Catalog: Cnvalue

5.286. nvalue

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

[PachetRoy99]

Constraint

$𝚗𝚟𝚊𝚕𝚞𝚎 (𝙽𝚅𝙰𝙻, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Synonyms

$𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚘𝚗_𝚊𝚝𝚝𝚛𝚒𝚋𝚞𝚝𝚎𝚜_𝚟𝚊𝚕𝚞𝚎𝚜$ , $𝚟𝚊𝚕𝚞𝚎𝚜$ .

Arguments

$𝙽𝚅𝙰𝙻$	$𝚍𝚟𝚊𝚛$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟𝚊𝚛)

𝙽𝚅𝙰𝙻 \geq 𝚖𝚒𝚗 (1, | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |)

𝙽𝚅𝙰𝙻 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝙽𝚅𝙰𝙻 \leq

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛)

Purpose

$𝙽𝚅𝙰𝙻$ is the number of distinct values taken by the variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Example

(4, 〈3, 1, 7, 1, 6〉)

(1, 〈6, 6, 6, 6, 6〉)

(5, 〈6, 3, 0, 2, 9〉)

The first $𝚗𝚟𝚊𝚕𝚞𝚎$ constraint holds since its first argument $𝙽𝚅𝙰𝙻 = 4$ is set to the number of distinct values occurring within the collection $〈 3, 1, 7, 1, 6 〉$ .
The second $𝚗𝚟𝚊𝚕𝚞𝚎$ constraint holds since its first argument $𝙽𝚅𝙰𝙻 = 1$ is set to the number of distinct values occurring within the collection $〈 6, 6, 6, 6, 6 〉$ .
The third $𝚗𝚟𝚊𝚕𝚞𝚎$ constraint holds since its first argument $𝙽𝚅𝙰𝙻 = 5$ is set to the number of distinct values occurring within the collection $〈 6, 3, 0, 2, 9 〉$ .

ctrs/nvalue-1-tikz

All solutions

Figure 5.286.1 gives all solutions to the following non ground instance of the $𝚗𝚟𝚊𝚕𝚞𝚎$ constraint: $N \in [1, 2]$ , $V_{1} \in [2, 4]$ , $V_{2} \in [1, 2]$ , $V_{3} \in [2, 4]$ , $𝚗𝚟𝚊𝚕𝚞𝚎$ $(N, 〈 V_{1}, V_{2}, V_{3} 〉)$ .

Figure 5.286.1. All solutions corresponding to the non ground example of the $𝚗𝚟𝚊𝚕𝚞𝚎$ constraint of the All solutions slot

Typical

𝙽𝚅𝙰𝙻 > 1

𝙽𝚅𝙰𝙻 < | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > 1

Symmetries

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are permutable.
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

Functional dependency: $𝙽𝚅𝙰𝙻$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .
Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙽𝚅𝙰𝙻 = 1$ and $| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > 0$ .
Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙽𝚅𝙰𝙻 = | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |$ .

Usage

The $𝚗𝚟𝚊𝚕𝚞𝚎$ constraint allows relaxing the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint by restricting its first argument $𝙽𝚅𝙰𝙻$ to be close, but not necessarily equal, to the number of variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection.

A classical example from the early 1850s is the dominating queens chess puzzle problem: Place a number of queens on an $n$ by $n$ chessboard in such a way that all cells of the chessboard are either attacked by a queen or are occupied by a queen. A queen can attack all cells located on the same column, on the same row or on the same diagonal. Part (A) of Figure 5.286.2 illustrates a set of five queens which together attack all of the cells of an 8 by 8 chessboard. The dominating queens problem can be modelled by just one $𝚗𝚟𝚊𝚕𝚞𝚎$ constraint:

We first label the different cells of the chessboard from 1 to $n^{2}$ .
We then associate to each cell $c$ of the chessboard a domain variable. Its initial domain is set to the labels of the cells that can attack cell $c$ . For instance, in the context of an 8 by 8 chessboard, the initial domain of $V_{29}$ will be set to {2,5,8,11,13,15,20..22,25..32,36..38,43,45,47,50,53,56,57,61} (see the green cells of part (B) of Figure 5.286.2).
Finally, we post the constraint $𝚗𝚟𝚊𝚕𝚞𝚎$ $(Q, 〈 𝚟𝚊𝚛 - V_{1}, 𝚟𝚊𝚛 - V_{2}, \dots, 𝚟𝚊𝚛 - V_{n^{2}} 〉)$ where $Q$ is a domain variable in $[1, n^{2}]$ that gives the total number of queens used for controlling all cells of the chessboard. For the solution depicted by Part (A) of Figure 5.286.2, the label in each cell of Part (C) of Figure 5.286.2 gives the value assigned to the corresponding variable. Note that, since a given cell can be attacked by several queens, we have also other assignments corresponding to the solution depicted by Part (A) of Figure 5.286.2.

Figure 5.286.2. Modelling the dominating queens problem with a single $𝚗𝚟𝚊𝚕𝚞𝚎$ constraint; (A) a solution to the dominating queens problem, (B) the initial domain (in bold) of the variable associated with cell 29: in a solution the value $j$ assigned to the variable associated with cell $i$ represents the label of the cell attacking cell $i$ (i.e. in a solution one of the selected queens is located on cell $j$ ), (C) the value of each cell in the model with one single $𝚗𝚟𝚊𝚕𝚞𝚎$ constraint corresponding to the solution depicted in (A).

The $𝚗𝚟𝚊𝚕𝚞𝚎$ constraint occurs also in many practical applications. In the context of timetabling one wants to set up a limit on the maximum number of activity types it is possible to perform. For frequency allocation problems, one optimisation criterion is to minimise the number of distinct frequencies that you use all over the entire network.

The $𝚗𝚟𝚊𝚕𝚞𝚎$ constraint generalises several constraints like:

$𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ : in order to get the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint, one has to set $𝙽𝚅𝙰𝙻$ to the total number of variables.
$𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ : in order to get the $𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ constraint, one has to set the minimum value of $𝙽𝚅𝙰𝙻$ to 2.

Remark

This constraint appears in [PachetRoy99] under the name of Cardinality on Attributes Values. The $𝚗𝚟𝚊𝚕𝚞𝚎$ constraint is called $𝚟𝚊𝚕𝚞𝚎𝚜$ in JaCoP (http://www.jacop.eu/). A constraint called $𝚔_𝚍𝚒𝚏𝚏$ enforcing that a set of variables takes at least $k$ distinct values appears in the PhD thesis of J.-C. Régin [Regin95].

It was shown in [BessiereHebrardHnichWalshO4] that, finding out whether a $𝚗𝚟𝚊𝚕𝚞𝚎$ constraint has a solution or not is NP-hard. This was achieved by reduction from 3-SAT. In the same article, it is also shown, by reduction from minimum hitting set cardinality, that computing a sharp lower bound on $𝙽𝚅𝙰𝙻$ is NP-hard.

Both reformulations of the $𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍_𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎$ constraint and of the $𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍_𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜$ constraint use the $𝚗𝚟𝚊𝚕𝚞𝚎$ constraint.

Algorithm

A first filtering algorithm for the $𝚗𝚟𝚊𝚕𝚞𝚎$ constraint was described in [Beldiceanu01]. Assuming that the minimum value of variable $𝙽𝚅𝙰𝙻$ is not constrained at all, two algorithms that both achieve bound-consistency were provided one year later in [BeldiceanuCarlssonThiel02]. Under the same assumption, algorithms that partially take into account holes in the domains of the variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection are described in [BeldiceanuCarlssonThiel02], [BessiereHebrardHnichKiziltanWalsh05].

Reformulation

A model, involving linear inequalities constraints, preserving bound-consistency was introduced in [BessiereKatsirelosNarodytskaQuimperWalsh10CP].

Counting

Length ( $n$ )	2	3	4	5	6	7	8
Solutions	9	64	625	7776	117649	2097152	43046721

Number of solutions for $𝚗𝚟𝚊𝚕𝚞𝚎$ : domains $0 . . n$

ctrs/nvalue-4-tikz

ctrs/nvalue-5-tikz

Length (

n

)

Total

625

7776

117649

2097152

43046721

Parameter

value

140

450

1302

3528

9144

360

3000

18900

101136

486864

120

3600

54600

588000

5143824

720

37800

940800

15876000

5040

423360

16087680

40320

5080320

362880

Solution count for $𝚗𝚟𝚊𝚕𝚞𝚎$ : domains $0 . . n$

ctrs/nvalue-6-tikz

ctrs/nvalue-7-tikz

Systems

nvalues in Gecode, nvalue in MiniZinc, nvalue in SICStus.

Used in

$𝚝𝚛𝚊𝚌𝚔$ .

common keyword: $𝚊𝚖𝚘𝚗𝚐$ , $𝚊𝚖𝚘𝚗𝚐_𝚍𝚒𝚏𝚏_0$ , $𝚌𝚘𝚞𝚗𝚝$ , $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ , $𝚖𝚊𝚡_𝚗𝚟𝚊𝚕𝚞𝚎$ , $𝚖𝚒𝚗_𝚗𝚟𝚊𝚕𝚞𝚎$ (counting constraint), $𝚗𝚟𝚊𝚕𝚞𝚎𝚜_𝚎𝚡𝚌𝚎𝚙𝚝_0$ (counting constraint,number of distinct values).

cost variant: $𝚜𝚞𝚖_𝚘𝚏_𝚠𝚎𝚒𝚐𝚑𝚝𝚜_𝚘𝚏_𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝_𝚟𝚊𝚕𝚞𝚎𝚜$ (introduce a weight for each value and replace number of distinct values by sum of weights associated with distinct values).

generalisation: $𝚗𝚌𝚕𝚊𝚜𝚜$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 \in 𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ ), $𝚗𝚎𝚚𝚞𝚒𝚟𝚊𝚕𝚎𝚗𝚌𝚎$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 \mod 𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝$ ), $𝚗𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 / 𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝$ ), $𝚗𝚙𝚊𝚒𝚛$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ replaced by $𝚙𝚊𝚒𝚛$ of $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜$ ), $𝚗𝚟𝚊𝚕𝚞𝚎𝚜$ (replace an equality with the number of distinct values by a comparison with the number of distinct values), $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ (variable replaced by vector).

implied by: $𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚗𝚟𝚊𝚕𝚞𝚎$ .

implies: $𝚊𝚝𝚕𝚎𝚊𝚜𝚝_𝚗𝚟𝚊𝚕𝚞𝚎$ ( $= 𝙽𝚅𝙰𝙻$ replaced by $\geq 𝙽𝚅𝙰𝙻$ ), $𝚊𝚝𝚖𝚘𝚜𝚝_𝚗𝚟𝚊𝚕𝚞𝚎$ ( $= 𝙽𝚅𝙰𝙻$ replaced by $\leq 𝙽𝚅𝙰𝙻$ ).

related: $𝚋𝚊𝚕𝚊𝚗𝚌𝚎$ (restriction on how balanced an assignment is), $𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍_𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎$ (restrict number of distinct colours on each maximum clique of the interval graph associated with the tasks), $𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍_𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜$ (restrict number of distinct colours on each maximum clique of the interval graph associated with the tasks assigned to the same machine), $𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚗𝚟𝚊𝚕𝚞𝚎_𝚌𝚑𝚊𝚒𝚗$ , $𝚔_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ (necessary condition for two overlapping $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraints), $𝚜𝚘𝚏𝚝_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚟𝚊𝚛$ .

shift of concept: $𝚗𝚟𝚊𝚕𝚞𝚎_𝚘𝚗_𝚒𝚗𝚝𝚎𝚛𝚜𝚎𝚌𝚝𝚒𝚘𝚗$ .

soft variant: $𝚗𝚟𝚊𝚕𝚞𝚎𝚜_𝚎𝚡𝚌𝚎𝚙𝚝_0$ (value 0 is ignored).

specialisation: $𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ (enforce to have one single value), $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ (enforce a number of distinct values equal to the number of variables), $𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ (enforce to have at least two distinct values).

uses in its reformulation: $𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎_𝚟𝚊𝚕𝚞𝚎𝚜$ , $𝚌𝚢𝚌𝚕𝚎$ , $𝚖𝚒𝚗_𝚗$ .

Keywords

characteristic of a constraint: core, automaton, automaton with array of counters.

complexity: 3-SAT, minimum hitting set cardinality.

constraint arguments: pure functional dependency.

constraint type: counting constraint, value partitioning constraint.

filtering: bound-consistency, convex bipartite graph.

final graph structure: strongly connected component, equivalence.

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

problems: domination.

puzzles: dominating queens.

Cond. implications

$𝚗𝚟𝚊𝚕𝚞𝚎 (𝙽𝚅𝙰𝙻, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

with $𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

implies $𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚗𝚟𝚊𝚕𝚞𝚎$ $(𝙽𝚅𝙰𝙻, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ .

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.286.3 respectively show the initial and final graph associated with the first example of 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 4 following values 1, 3, 6 and 7 are used by the variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection.

Figure 5.286.3. Initial and final graph of the $𝚗𝚟𝚊𝚕𝚞𝚎$ constraint


(a)	(b)

Automaton

Figure 5.286.4 depicts the automaton associated with the $𝚗𝚟𝚊𝚕𝚞𝚎$ constraint. To each item of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ corresponds a signature variable $S_{i}$ that is equal to 0.