5.17. among_diff_0

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Used in the automaton of πš—πšŸπšŠπš•πšžπšŽ.

Constraint

πšŠπš–πš˜πš—πš_πšπš’πšπš_0(π™½πš…π™°πš,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

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

π™½πš…π™°πš is the number of variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ that take a value different from 0.

Example
(3,0,5,5,0,1)

The πšŠπš–πš˜πš—πš_πšπš’πšπš_0 constraint holds since exactly 3 values of the collection of values 〈0,5,5,0,1βŒͺ are different from 0.

Typical
π™½πš…π™°πš>0
π™½πš…π™°πš<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πšŠπšπš•πšŽπšŠπšœπš(1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,0)
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

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

See also

common keyword: πš—πšŸπšŠπš•πšžπšŽΒ (counting constraint).

generalisation: πšŠπš–πš˜πš—πšΒ (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽβ‰ 0 replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽβˆˆπšŸπšŠπš•πšžπšŽπšœ).

Keywords

characteristic of a constraint: joker value, 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)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›β‰ 0
Graph property(ies)
𝐍𝐀𝐑𝐂=π™½πš…π™°πš

Graph model

Since this is a unary constraint we employ the 𝑆𝐸𝐿𝐹 arc generator in order to produce an initial graph with a single loop on each vertex.

PartsΒ (A) andΒ (B) of FigureΒ 5.17.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.17.1. Initial and final graph of the πšŠπš–πš˜πš—πš_πšπš’πšπš_0 constraint
ctrs/among_diff_0Actrs/among_diff_0B
(a) (b)
Automaton

FigureΒ 5.17.2 depicts the automaton associated with the πšŠπš–πš˜πš—πš_πšπš’πšπš_0 constraint. To each variable πš…π™°πš i of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a 0-1 signature variable πš‚ i . The following signature constraint links πš…π™°πš i and πš‚ i : πš…π™°πš i β‰ 0β‡”πš‚ i . The automaton counts the number of variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection that take a value different from 0 and finally assigns this number to π™½πš…π™°πš.

Figure 5.17.2. Automaton of the πšŠπš–πš˜πš—πš_πšπš’πšπš_0 constraint
ctrs/among_diff_01
Figure 5.17.3. Hypergraph of the reformulation corresponding to the automaton of the πšŠπš–πš˜πš—πš_πšπš’πšπš_0 constraint
ctrs/among_diff_02