5.310. soft_used_by_modulo_var

DESCRIPTIONLINKSGRAPH
Origin

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

Constraint

𝚜𝚘𝚏𝚝_𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜_πšŸπšŠπš›(𝙲,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2,𝙼)

Synonym

𝚜𝚘𝚏𝚝_𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜.

Arguments
π™²πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
π™Όπš’πš—πš
Restrictions
𝙲β‰₯0
𝙲≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|β‰₯|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2,πšŸπšŠπš›)
𝙼>0
Purpose

For each integer R in [0,𝙼-1], let 𝑁1 R (respectively 𝑁2 R ) denote the number of variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 (respectively πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2) that have R as a rest when divided by 𝙼. 𝙲 is the minimum number of values to change in the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 collections so that for all R in [0,𝙼-1] we have 𝑁2 R >0⇒𝑁1 R >0.

Example
2,9,1,1,8,8,9,9,9,1,3

In the example, the values of the collections 〈9,1,1,8,8βŒͺ and 〈9,9,9,1βŒͺ are respectively associated with the equivalence classes 9 mod 3=0, 1 mod 3=1, 1 mod 3=1, 8 mod 3=2, 8 mod 3=2 and 9 mod 3=0, 9 mod 3=0, 9 mod 3=0, 1 mod 3=1. Since there is a correspondence between two pairs of equivalence classes we must unset at least 4-2 items (4 is the number of items of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 collection). Consequently, the 𝚜𝚘𝚏𝚝_𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜_πšŸπšŠπš› constraint holds since its first argument 𝙲 is set to 4-2.

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

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

  • An occurrence of a value u of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.πšŸπšŠπš› can be replaced by any other value v such that v is congruent to u modulo 𝙼.

  • An occurrence of a value u of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.πšŸπšŠπš› can be replaced by any other value v such that v is congruent to u modulo 𝙼.

Usage

A soft 𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜ constraint.

See also

hard version: 𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜.

implied by: 𝚜𝚘𝚏𝚝_πšœπšŠπš–πšŽ_πš–πš˜πšπšžπš•πš˜_πšŸπšŠπš›.

Keywords

characteristic of a constraint: modulo.

constraint arguments: constraint between two collections of variables.

constraint type: soft constraint, relaxation, variable-based violation measure.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš› mod 𝙼=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš› mod 𝙼
Graph property(ies)
ππ’πˆππŠ_ππ’πŽπ”π‘π‚π„=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|-𝙲

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.310.1 respectively show the initial and final graph associated with the Example slot. Since we use the ππ’πˆππŠ_ππ’πŽπ”π‘π‚π„ graph property, the source and sink vertices of the final graph are stressed with a double circle. The 𝚜𝚘𝚏𝚝_𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜_πšŸπšŠπš› constraint holds since the cost 2 corresponds to the difference between the number of variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 and the sum over the different connected components of the minimum number of sources and sinks.

Figure 5.310.1. Initial and final graph of the 𝚜𝚘𝚏𝚝_𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜_πšŸπšŠπš› constraint
ctrs/soft_used_by_modulo_varActrs/soft_used_by_modulo_varB
(a) (b)