5.238. nvalue

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

[PachetRoy99]

Constraint

πš—πšŸπšŠπš•πšžπšŽ(π™½πš…π™°π™»,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Synonyms

πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš˜πš—_πšŠπšπšπš›πš’πš‹πšžπšπšŽπšœ_πšŸπšŠπš•πšžπšŽπšœ, πšŸπšŠπš•πšžπšŽπšœ.

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

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

Example
(4,3,1,7,1,6)

The πš—πšŸπšŠπš•πšžπšŽ constraint holds since its first argument π™½πš…π™°π™»=4 is set to the number of distinct values occurring within the collection 〈3,1,7,1,6βŒͺ.

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.

Usage

A classical example from the early 1850s is the dominating queens chess puzzle problem: Place a number of queens on a n by n chessboard in such a way that all squares are either attacked by a queen or are occupied by a queen. A queen can attack all squares located on the same column, on the same row or on the same diagonal. PartΒ (A) of FigureΒ 5.238.1 illustrates a set of five queens which together attack all of the squares of an 8 by 8 chessboard. The dominating queens problem can be modelled as one single πš—πšŸπšŠπš•πšžπšŽ constraint:

  • We first label the different squares of the chessboard from 1 to n 2 .

  • We then associate to each square S of the chessboard a domain variable. Its initial domain is set to the numbers of the squares that can be attacked from S. 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 squares of partΒ (B) of FigureΒ 5.238.1).

  • Finally, we post the constraint πš—πšŸπšŠπš•πšžπšŽ(Q,βŒ©πšŸπšŠπš›-V 1 ,πšŸπšŠπš›-V 2 ,...,πšŸπšŠπš›-V n 2 βŒͺ) where Q is a domain variable in [1,n 2 ] that gives the total number of queens used for controlling all squares of the chessboard. For the solution depicted by PartΒ (A) of FigureΒ 5.238.1, the number in each square of PartΒ (C) of FigureΒ 5.238.1 gives the value assigned to the corresponding variable. Note that, since a given square can be attacked by several queens, we have also other assignments corresponding to the solution depicted by PartΒ (A) of FigureΒ 5.238.1.

Figure 5.238.1. Modelling the dominating queens problem with one single πš—πšŸπšŠπš•πšžπšŽ constraint
ctrs/nvalue2

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 criteria corresponds to the fact that you want to minimise the number of distinct frequencies that you use all over the entire network. The πš—πšŸπšŠπš•πšžπšŽ constraint generalises several constraints like:

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].

Systems

nvalue in SICStus.

Used in

πšπš›πšŠπšŒπš”.

See also

assignment dimension added: πšŠπšœπšœπš’πšπš—_πšŠπš—πš_πš—πšŸπšŠπš•πšžπšŽπšœ.

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 πšŸπšŠπš›πš’πšŠπš‹πš•πšŽβˆˆπš™πšŠπš›πšπš’πšπš’πš˜πš—), πš—πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πšŒπšŽΒ (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ 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 β‰₯π™½πš…π™°π™»), πšŠπšπš–πš˜πšœπš_πš—πšŸπšŠπš•πšžπšŽΒ (=π™½πš…π™°π™» replaced by β‰€π™½πš…π™°π™»).

related: πšŒπš˜πš•πš˜πšžπš›πšŽπš_πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽΒ (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 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.

problems: domination.

puzzles: dominating queens.

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.238.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 4 following values 1, 3, 6 and 7 are used by the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection.

Figure 5.238.2. Initial and final graph of the πš—πšŸπšŠπš•πšžπšŽ constraint
ctrs/nvalueActrs/nvalueB
(a) (b)
Automaton

FigureΒ 5.238.3 depicts the automaton associated with the πš—πšŸπšŠπš•πšžπšŽ constraint. To each item of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a signature variable πš‚ i that is equal to 0.

Figure 5.238.3. Automaton of the πš—πšŸπšŠπš•πšžπšŽ constraint
ctrs/nvalue1