5.30. atleast_nvalue

DESCRIPTIONLINKSGRAPH
Origin

[Regin95]

Constraint

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

Synonym

πš”_πšπš’πšπš.

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

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

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

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

Typical
π™½πš…π™°π™»>0
π™½πš…π™°π™»<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
Symmetries
  • π™½πš…π™°π™» can be decreased to any value β‰₯0.

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

Remark

The πšŠπšπš•πšŽπšŠπšœπš_πš—πšŸπšŠπš•πšžπšŽ constraint was first introduced by J.-C.Β RΓ©gin under the name πš”_πšπš’πšπš inΒ [Regin95]. Later on the πšŠπšπš•πšŽπšŠπšœπš_πš—πšŸπšŠπš•πšžπšŽ constraint was introduced together with the πšŠπšπš–πš˜πšœπš_πš—πšŸπšŠπš•πšžπšŽ constraint by C.Β BessiΓ¨re et al. in a articleΒ [BessiereHebrardHnichKiziltanWalsh05] providing filtering algorithms for the πš—πšŸπšŠπš•πšžπšŽ constraint.

Algorithm

[BessiereHebrardHnichKiziltanWalsh05] provides a sketch of a filtering algorithm enforcing arc-consistency for the πšŠπšπš•πšŽπšŠπšœπš_πš—πšŸπšŠπš•πšžπšŽ constraint. This algorithm is based on the maximal matching in a bipartite graph.

See also

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

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

uses in its reformulation: πš—πš˜πš_πšŠπš•πš•_πšŽπššπšžπšŠπš•.

Keywords

constraint type: counting constraint, value partitioning constraint.

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

Figure 5.30.1. Initial and final graph of the πšŠπšπš•πšŽπšŠπšœπš_πš—πšŸπšŠπš•πšžπšŽ constraint
ctrs/atleast_nvalueA
(a)
ctrs/atleast_nvalueB
(b)