5.29. atleast

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

CHIP

Constraint

πšŠπšπš•πšŽπšŠπšœπš(𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄)

Synonym

πšŒπš˜πšžπš—πš.

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

At least 𝙽 variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection are assigned value πš…π™°π™»πš„π™΄.

Example
(2,4,2,4,5,4)

The πšŠπšπš•πšŽπšŠπšœπš constraint holds since at least 2 values of the collection 〈4,2,4,5βŒͺ are equal to value 4.

Typical
𝙽>0
𝙽<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

  • 𝙽 can be decreased to any value β‰₯0.

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

Systems

occurenceMin in Choco, count in Gecode, count in JaCoP, count in SICStus.

Used in

πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0, πšŠπš–πš˜πš—πš_πšπš’πšπš_0, πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ, πš’πšπš‘_πš™πš˜πšœ_πšπš’πšπšπšŽπš›πšŽπš—πš_πšπš›πš˜πš–_0.

See also

common keyword: πšŠπš–πš˜πš—πšΒ (value constraint).

comparison swapped: πšŠπšπš–πš˜πšœπš.

implied by: πšŽπš‘πšŠπšŒπšπš•πš’Β (β‰₯ 𝙽 replaced by = 𝙽).

related: πš›πš˜πš˜πšπšœ.

soft variant: πš˜πš™πšŽπš—_πšŠπšπš•πšŽπšŠπšœπšΒ (open constraint).

Keywords

characteristic of a constraint: automaton, automaton with counters.

constraint network structure: alpha-acyclic constraint network(2).

constraint type: value constraint.

filtering: arc-consistency.

modelling: at least.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generator
π‘†πΈπΏπΉβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›=πš…π™°π™»πš„π™΄
Graph property(ies)
𝐍𝐀𝐑𝐂β‰₯𝙽

Graph model

Since each arc constraint involves only one vertex (πš…π™°π™»πš„π™΄ is fixed), we employ the 𝑆𝐸𝐿𝐹 arc generator in order to produce a graph with a single loop on each vertex.

PartsΒ (A) andΒ (B) of FigureΒ 5.29.1 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property, the loops of the final graph are stressed in bold.

Figure 5.29.1. Initial and final graph of the πšŠπšπš•πšŽπšŠπšœπš constraint
ctrs/atleastActrs/atleastB
(a) (b)
Automaton

FigureΒ 5.29.2 depicts the automaton associated with the πšŠπšπš•πšŽπšŠπšœπš constraint. To each variable πš…π™°πš i of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a 0-1 signature variable πš‚ i . The following signature constraint links πš…π™°πš i and πš‚ i : πš…π™°πš i =πš…π™°π™»πš„π™΄β‡”πš‚ i . The automaton counts the number of variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection that are assigned value πš…π™°π™»πš„π™΄ and finally checks that this number is greater than or equal to 𝙽.

Figure 5.29.2. Automaton of the πšŠπšπš•πšŽπšŠπšœπš constraint
ctrs/atleast1
Figure 5.29.3. Hypergraph of the reformulation corresponding to the automaton of the πšŠπšπš•πšŽπšŠπšœπš constraint
ctrs/atleast2