5.34. atmost_nvalue

DESCRIPTIONLINKSGRAPH
Origin

[BessiereHebrardHnichKiziltanWalsh05]

Constraint

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

Synonyms

𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπš_πš–πšŠπš‘_πšŸπšŠπš›, 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš–πšŠπš‘_πšŸπšŠπš›, 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšœπšπš’πš—πšŒπš_πš–πšŠπš‘_πšŸπšŠπš›.

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

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

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

The πšŠπšπš–πš˜πšœπš_πš—πšŸπšŠπš•πšžπšŽ constraint holds since the collection 〈3,1,3,1,6βŒͺ involves at most 4 distinct values (i.e.,Β in fact 3 distinct values).

Typical
π™½πš…π™°π™»>1
π™½πš…π™°π™»<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
Symmetries
  • π™½πš…π™°π™» can be increased.

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

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› can be replaced by any value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›.

Remark

This constraint was introduced together with the πšŠπšπš•πšŽπšŠπšœπš_πš—πšŸπšŠπš•πšžπšŽ constraint by C.Β BessiΓ¨re et al. in a articleΒ [BessiereHebrardHnichKiziltanWalsh05] providing filtering algorithms for the πš—πšŸπšŠπš•πšžπšŽ constraint.

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.

Algorithm

[Beldiceanu01] provides an algorithm that achieves bound consistency. [BeldiceanuCarlssonThiel02] provides two filtering algorithms, whileΒ [BessiereHebrardHnichKiziltanWalsh05] provides a greedy algorithm and a graph invariant for evaluating the minimum number of distinct values. [BessiereHebrardHnichKiziltanWalsh05] also gives a linear relaxation for approximating the minimum number of distinct values.

Systems

atMostNValue in Choco.

See also

comparison swapped: πšŠπšπš•πšŽπšŠπšœπš_πš—πšŸπšŠπš•πšžπšŽ.

implied by: πš—πšŸπšŠπš•πšžπšŽΒ (≀ π™½πš…π™°π™» replaced by = π™½πš…π™°π™»).

related: 𝚜𝚘𝚏𝚝_πšŠπš•πš•_πšŽπššπšžπšŠπš•_πš–πšŠπš‘_πšŸπšŠπš›, 𝚜𝚘𝚏𝚝_πšŠπš•πš•_πšŽπššπšžπšŠπš•_πš–πš’πš—_πšŒπšπš›, 𝚜𝚘𝚏𝚝_πšŠπš•πš•_πšŽπššπšžπšŠπš•_πš–πš’πš—_πšŸπšŠπš›, 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŒπšπš›, 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŸπšŠπš›.

Keywords

complexity: 3-SAT.

constraint type: counting constraint, value partitioning constraint.

filtering: bound-consistency.

final graph structure: strongly connected component, equivalence.

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

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.34.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 specific value that is assigned to some variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. The 3 following values 1, 3 and 6 are used by the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection.

Figure 5.34.1. Initial and final graph of the πšŠπšπš–πš˜πšœπš_πš—πšŸπšŠπš•πšžπšŽ constraint
ctrs/atmost_nvalueA
(a)
ctrs/atmost_nvalueB
(b)