5.184. k_used_by_modulo

DESCRIPTIONLINKSGRAPH
Origin

Derived from 𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜ and from πš”_𝚞𝚜𝚎𝚍_πš‹πš’.

Constraint

πš”_𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜(πš‚π™΄πšƒπš‚,𝙼)

Type
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Arguments
πš‚π™΄πšƒπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚜𝚎𝚝-πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)
π™Όπš’πš—πš
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>0
πš›πšŽπššπšžπš’πš›πšŽπš(πš‚π™΄πšƒπš‚,𝚜𝚎𝚝)
|πš‚π™΄πšƒπš‚|>1
πš—πš˜πš—_πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšœπš’πš£πšŽ(πš‚π™΄πšƒπš‚,𝚜𝚎𝚝)
𝙼>0
Purpose

Given |πš‚π™΄πšƒπš‚| sets of domain variables, the πš”_𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜ constraint enforces a 𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜ constraint between each pair of consecutive sets.

Example
𝚜𝚎𝚝-πšŸπšŠπš›-1,πšŸπšŠπš›-9,πšŸπšŠπš›-4,πšŸπšŠπš›-5,πšŸπšŠπš›-2,πšŸπšŠπš›-1,𝚜𝚎𝚝-7,1,2,5,𝚜𝚎𝚝-1,1,3

The πš”_𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜ constraint holds since:

  • The first collection of variables is assigned 1 value in {0,3,...,3Β·k}, 3 values in {1,4,...,1+3Β·k} and 2 values in {2,5,...,2+3Β·k}, while the second collection of variables is assigned no more values in the previous three sets of values.

  • The second collection of variables is assigned 2 values in {0,3,...,3Β·k} and 2 values in {2,5,...,2+3Β·k}, while the third collection of variables is assigned no more values in the previous three sets of values.

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

  • Items of πš‚π™΄πšƒπš‚.𝚜𝚎𝚝 are permutable.

  • An occurrence of a value u of πš‚π™΄πšƒπš‚.𝚜𝚎𝚝.πšŸπšŠπš› can be replaced by any other value v such that v is congruent to u modulo 𝙼.

See also

common keyword: πš”_𝚞𝚜𝚎𝚍_πš‹πš’Β (system of constraints).

part of system of constraints: 𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜.

used in graph description: 𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜.

Keywords

characteristic of a constraint: modulo.

constraint type: system of constraints, decomposition.

modelling: inclusion.

Arc input(s)

πš‚π™΄πšƒπš‚

Arc generator
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚜𝚎𝚝1,𝚜𝚎𝚝2)

Arc arity
Arc constraint(s)
𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜(𝚜𝚎𝚝1.𝚜𝚎𝚝,𝚜𝚎𝚝2.𝚜𝚎𝚝,𝙼)
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš‚π™΄πšƒπš‚|-1

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.184.1 respectively show the initial and final graph associated with the Example slot. To each vertex corresponds a collection of variables, while to each arc corresponds a 𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜ constraint.

Figure 5.184.1. Initial and final graph of the πš”_𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜ constraint
ctrs/k_used_by_moduloActrs/k_used_by_moduloB
(a) (b)