5.32. atmost

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

CHIP

Constraint

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

Synonym

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

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

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

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

The πšŠπšπš–πš˜πšœπš constraint holds since at most 1 value of the collection 〈4,2,4,5βŒͺ is equal to value 2.

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

  • 𝙽 can be increased.

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

Systems

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

See also

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

comparison swapped: πšŠπšπš•πšŽπšŠπšœπš.

generalisation: πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽΒ (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšπšŠπšœπš”).

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

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.32.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.32.1. Initial and final graph of the πšŠπšπš–πš˜πšœπš constraint
ctrs/atmostActrs/atmostB
(a) (b)
Automaton

FigureΒ 5.32.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 less than or equal to 𝙽.

Figure 5.32.2. Automaton of the πšŠπšπš–πš˜πšœπš constraint
ctrs/atmost1
Figure 5.32.3. Hypergraph of the reformulation corresponding to the automaton of the πšŠπšπš–πš˜πšœπš constraint
ctrs/atmost2