5.78. counts

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

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

Constraint

πšŒπš˜πšžπš—πšπšœ(πš…π™°π™»πš„π™΄πš‚,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšπ™΄π™»π™Ύπ™Ώ,π™»π™Έπ™Όπ™Έπšƒ)

Arguments
πš…π™°π™»πš„π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•-πš’πš—πš)
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πšπ™΄π™»π™Ύπ™ΏπšŠπšπš˜πš–
π™»π™Έπ™Όπ™ΈπšƒπšπšŸπšŠπš›
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
πšπš’πšœπšπš’πš—πšŒπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
πšπ™΄π™»π™Ύπ™Ώβˆˆ[=,β‰ ,<,β‰₯,>,≀]
Purpose

Let N be the number of variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection assigned to a value of the πš…π™°π™»πš„π™΄πš‚ collection. Enforce condition N πšπ™΄π™»π™Ύπ™Ώ π™»π™Έπ™Όπ™Έπšƒ to hold.

Example
1,3,4,9,πšŸπšŠπš›-4,πšŸπšŠπš›-5,πšŸπšŠπš›-5,πšŸπšŠπš›-4,πšŸπšŠπš›-1,πšŸπšŠπš›-5,=,3

Values 1, 3, 4 and 9 of the πš…π™°π™»πš„π™΄πš‚ collection are assigned to 3 items of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚=〈4,5,5,4,1,5βŒͺ collection. The πšŒπš˜πšžπš—πšπšœ constraint holds since this number is in fact equal (πšπ™΄π™»π™Ύπ™Ώ is set to =) to the last argument of the πšŒπš˜πšžπš—πšπšœ constraint.

Typical
|πš…π™°π™»πš„π™΄πš‚|>1
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>|πš…π™°π™»πš„π™΄πš‚|
π™»π™Έπ™Όπ™Έπšƒ>0
π™»π™Έπ™Όπ™Έπšƒ<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
Symmetries
  • Items of πš…π™°π™»πš„π™΄πš‚ are permutable.

  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› that belongs to πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš• (resp. does not belong to πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•) can be replaced by any other value in πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš• (resp. not in πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•).

Usage

Used in the Constraint(s) on sets slot for defining some constraints like πšŠπšœπšœπš’πšπš—_πšŠπš—πš_πšŒπš˜πšžπš—πšπšœ.

Reformulation

The πšŒπš˜πšžπš—πš(πš…π™°π™»πš„π™΄πš‚,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚, πšπ™΄π™»π™Ύπ™Ώ ,π™»π™Έπ™Όπ™Έπšƒ) constraint can be expressed in term of the conjunction πšŠπš–πš˜πš—πš(N,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚) ∧ N πšπ™΄π™»π™Ύπ™Ώ π™»π™Έπ™Όπ™Έπšƒ.

Used in

πšŠπšœπšœπš’πšπš—_πšŠπš—πš_πšŒπš˜πšžπš—πšπšœ.

See also

assignment dimension added: πšŠπšœπšœπš’πšπš—_πšŠπš—πš_πšŒπš˜πšžπš—πšπšœΒ (assignment dimension introduced).

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

specialisation: πšŒπš˜πšžπš—πšΒ (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽβˆˆπš…π™°π™»πš„π™΄πš‚ 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.

final graph structure: acyclic, bipartite, no loop.

Arc input(s)

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

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ,πšŸπšŠπš•πšžπšŽπšœ)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›=πšŸπšŠπš•πšžπšŽπšœ.πšŸπšŠπš•
Graph property(ies)
𝐍𝐀𝐑𝐂 πšπ™΄π™»π™Ύπ™Ώ π™»π™Έπ™Όπ™Έπšƒ

Graph class
β€’ π™°π™²πšˆπ™²π™»π™Έπ™²
β€’ π™±π™Έπ™Ώπ™°πšπšƒπ™Έπšƒπ™΄
β€’ 𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

Because of the arc constraint πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›=πšŸπšŠπš•πšžπšŽπšœ.πšŸπšŠπš• and since each domain variable can take at most one value, 𝐍𝐀𝐑𝐂 is the number of variables taking a value in the πš…π™°π™»πš„π™΄πš‚ collection.

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

Figure 5.78.1. Initial and final graph of the πšŒπš˜πšžπš—πšπšœ constraint
ctrs/countsActrs/countsB
(a) (b)
Automaton

FigureΒ 5.78.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.78.2. Automaton of the πšŒπš˜πšžπš—πšπšœ constraint
ctrs/counts1
Figure 5.78.3. Hypergraph of the reformulation corresponding to the automaton of the πšŒπš˜πšžπš—πšπšœ constraint
ctrs/counts2