5.20. among_modulo

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from πšŠπš–πš˜πš—πš.

Constraint

πšŠπš–πš˜πš—πš_πš–πš˜πšπšžπš•πš˜(π™½πš…π™°πš,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšπ™΄π™Όπ™°π™Έπ™½π™³π™΄πš,πš€πš„π™Ύπšƒπ™Έπ™΄π™½πšƒ)

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

π™½πš…π™°πš is the number of variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ taking a value that is congruent to πšπ™΄π™Όπ™°π™Έπ™½π™³π™΄πš modulo πš€πš„π™Ύπšƒπ™Έπ™΄π™½πšƒ.

Example
(3,4,5,8,4,1,0,2)

In this example πšπ™΄π™Όπ™°π™Έπ™½π™³π™΄πš=0 and πš€πš„π™Ύπšƒπ™Έπ™΄π™½πšƒ=2 specifies that we count the number of even values taken by the different variables. As a consequence the πšŠπš–πš˜πš—πš_πš–πš˜πšπšžπš•πš˜ constraint holds since exactly 3 values of the collection 〈4,5,8,4,1βŒͺ are even.

Typical
π™½πš…π™°πš>0
π™½πš…π™°πš<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πš€πš„π™Ύπšƒπ™Έπ™΄π™½πšƒ>1
πš€πš„π™Ύπšƒπ™Έπ™΄π™½πšƒ<πš–πšŠπš‘πšŸπšŠπš•(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

  • An occurrence of a value u of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› such that u mod πš€πš„π™Ύπšƒπ™Έπ™΄π™½πšƒ=πšπ™΄π™Όπ™°π™Έπ™½π™³π™΄πš (resp. u mod πš€πš„π™Ύπšƒπ™Έπ™΄π™½πšƒβ‰ πšπ™΄π™Όπ™°π™Έπ™½π™³π™΄πš) can be replaced by any other value v such that v mod πš€πš„π™Ύπšƒπ™Έπ™΄π™½πšƒ=πšπ™΄π™Όπ™°π™Έπ™½π™³π™΄πš (resp. u mod πš€πš„π™Ύπšƒπ™Έπ™΄π™½πšƒβ‰ πšπ™΄π™Όπ™°π™Έπ™½π™³π™΄πš).

Remark

By giving explicitly all values v that satisfy the equality v mod πš€πš„π™Ύπšƒπ™Έπ™΄π™½πšƒ=πšπ™΄π™Όπ™°π™Έπ™½π™³π™΄πš, the πšŠπš–πš˜πš—πš_πš–πš˜πšπšžπš•πš˜ constraint can be modelled with the πšŠπš–πš˜πš—πš constraint. However the πšŠπš–πš˜πš—πš_πš–πš˜πšπšžπš•πš˜ constraint provides a more compact form.

See also

generalisation: πšŠπš–πš˜πš—πšΒ (list of πšŸπšŠπš•πšžπšŽπšœ 𝚟 such that 𝚟 mod πš€πš„π™Ύπšƒπ™Έπ™΄π™½πšƒ = πšπ™΄π™Όπ™°π™Έπ™½π™³π™΄πš replaced by list of πšŸπšŠπš•πšžπšŽπšœ).

Keywords

characteristic of a constraint: modulo, 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)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš› mod πš€πš„π™Ύπšƒπ™Έπ™΄π™½πšƒ=πšπ™΄π™Όπ™°π™Έπ™½π™³π™΄πš
Graph property(ies)
𝐍𝐀𝐑𝐂=π™½πš…π™°πš

Graph model

The arc constraint corresponds to a unary constraint. For this reason 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.20.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.20.1. Initial and final graph of the πšŠπš–πš˜πš—πš_πš–πš˜πšπšžπš•πš˜ constraint
ctrs/among_moduloActrs/among_moduloB
(a) (b)
Automaton

FigureΒ 5.20.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 mod πš€πš„π™Ύπšƒπ™Έπ™΄π™½πšƒ=πšπ™΄π™Όπ™°π™Έπ™½π™³π™΄πšβ‡”πš‚ i .

Figure 5.20.2. Automaton of the πšŠπš–πš˜πš—πš_πš–πš˜πšπšžπš•πš˜ constraint
ctrs/among_modulo1
Figure 5.20.3. Hypergraph of the reformulation corresponding to the automaton of the πšŠπš–πš˜πš—πš_πš–πš˜πšπšžπš•πš˜ constraint
ctrs/among_modulo2