5.132. exactly

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from πšŠπšπš•πšŽπšŠπšœπš and πšŠπšπš–πš˜πšœπš.

Constraint

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

Synonym

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

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

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

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

The πšŽπš‘πšŠπšŒπšπš•πš’ constraint holds since exactly 𝙽=2 variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚=〈4,2,4,5βŒͺ collection are assigned value πš…π™°π™»πš„π™΄=4.

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

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

Systems

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

See also

generalisation: πšŠπš–πš˜πš—πšΒ (πšŒπš˜πš—πšœπšπšŠπš—πš replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ and πšŸπšŠπš•πšžπšŽ replaced by πš•πš’πšœπš of πšŸπšŠπš•πšžπšŽπšœ).

implies: πšŠπšπš•πšŽπšŠπšœπšΒ (=𝙽 replaced by β‰₯𝙽), πšŠπšπš–πš˜πšœπšΒ (=𝙽 replaced by ≀𝙽).

Keywords

characteristic of a constraint: automaton, automaton with counters.

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

constraint type: value constraint, counting constraint.

filtering: arc-consistency.

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.132.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. The πšŽπš‘πšŠπšŒπšπš•πš’ constraint holds since exactly two variables are assigned value 4.

Figure 5.132.1. Initial and final graph of the πšŽπš‘πšŠπšŒπšπš•πš’ constraint
ctrs/exactlyActrs/exactlyB
(a) (b)
Automaton

FigureΒ 5.132.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 .

Figure 5.132.2. Automaton of the πšŽπš‘πšŠπšŒπšπš•πš’ constraint
ctrs/exactly1
Figure 5.132.3. Hypergraph of the reformulation corresponding to the automaton of the πšŽπš‘πšŠπšŒπšπš•πš’ constraint
ctrs/exactly2