5.99. differ_from_at_least_k_pos

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Inspired by [Frutos97].

Constraint

πšπš’πšπšπšŽπš›_πšπš›πš˜πš–_𝚊𝚝_πš•πšŽπšŠπšœπš_πš”_πš™πš˜πšœ(𝙺,πš…π™΄π™²πšƒπ™Ύπš1,πš…π™΄π™²πšƒπ™Ύπš2)

Type
πš…π™΄π™²πšƒπ™ΎπšπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Arguments
π™Ίπš’πš—πš
πš…π™΄π™²πšƒπ™Ύπš1πš…π™΄π™²πšƒπ™Ύπš
πš…π™΄π™²πšƒπ™Ύπš2πš…π™΄π™²πšƒπ™Ύπš
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπš,πšŸπšŠπš›)
𝙺β‰₯0
𝙺≀|πš…π™΄π™²πšƒπ™Ύπš1|
|πš…π™΄π™²πšƒπ™Ύπš1|=|πš…π™΄π™²πšƒπ™Ύπš2|
Purpose

Enforce two vectors πš…π™΄π™²πšƒπ™Ύπš1 and πš…π™΄π™²πšƒπ™Ύπš2 to differ from at least 𝙺 positions.

Example
2,2,5,2,0,3,6,2,1

The πšπš’πšπšπšŽπš›_πšπš›πš˜πš–_𝚊𝚝_πš•πšŽπšŠπšœπš_πš”_πš™πš˜πšœ constraint holds since the first and second vectors differ from 3 positions, which is greater than or equal to 𝙺=2.

Typical
𝙺>0
|πš…π™΄π™²πšƒπ™Ύπš1|>1
Symmetries
  • Arguments are permutable w.r.t. permutation (𝙺) (πš…π™΄π™²πšƒπ™Ύπš1,πš…π™΄π™²πšƒπ™Ύπš2).

  • 𝙺 can be decreased to any value β‰₯0.

  • Items of πš…π™΄π™²πšƒπ™Ύπš1 and πš…π™΄π™²πšƒπ™Ύπš2 are permutable (same permutation used).

Remark

Used in the Arc constraint(s) slot of the πšŠπš•πš•_πšπš’πšπšπšŽπš›_πšπš›πš˜πš–_𝚊𝚝_πš•πšŽπšŠπšœπš_πš”_πš™πš˜πšœ constraint.

Used in

πšŠπš•πš•_πšπš’πšπšπšŽπš›_πšπš›πš˜πš–_𝚊𝚝_πš•πšŽπšŠπšœπš_πš”_πš™πš˜πšœ.

See also

system of constraints: πšŠπš•πš•_πšπš’πšπšπšŽπš›_πšπš›πš˜πš–_𝚊𝚝_πš•πšŽπšŠπšœπš_πš”_πš™πš˜πšœ.

Keywords

characteristic of a constraint: vector, automaton, automaton with counters.

constraint network structure: alpha-acyclic constraint network(2).

constraint type: value constraint.

Arc input(s)

πš…π™΄π™²πšƒπ™Ύπš1 πš…π™΄π™²πšƒπ™Ύπš2

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

Arc arity
Arc constraint(s)
πšŸπšŽπšŒπšπš˜πš›1.πšŸπšŠπš›β‰ πšŸπšŽπšŒπšπš˜πš›2.πšŸπšŠπš›
Graph property(ies)
𝐍𝐀𝐑𝐂β‰₯𝙺

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.99.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.99.1. Initial and final graph of the πšπš’πšπšπšŽπš›_πšπš›πš˜πš–_𝚊𝚝_πš•πšŽπšŠπšœπš_πš”_πš™πš˜πšœ constraint
ctrs/differ_from_at_least_k_posActrs/differ_from_at_least_k_posB
(a) (b)
Automaton

FigureΒ 5.99.2 depicts the automaton associated with the πšπš’πšπšπšŽπš›_πšπš›πš˜πš–_𝚊𝚝_πš•πšŽπšŠπšœπš_πš”_πš™πš˜πšœ constraint. Let πš…π™°πš1 i and πš…π™°πš2 i be the i th variables of the πš…π™΄π™²πšƒπ™Ύπš1 and πš…π™΄π™²πšƒπ™Ύπš2 collections. To each pair of variables (πš…π™°πš1 i ,πš…π™°πš2 i ) corresponds a signature variable πš‚ i . The following signature constraint links πš…π™°πš1 i , πš…π™°πš2 i and πš‚ i : πš…π™°πš1 i =πš…π™°πš2 i β‡”πš‚ i .

Figure 5.99.2. Automaton of the πšπš’πšπšπšŽπš›_πšπš›πš˜πš–_𝚊𝚝_πš•πšŽπšŠπšœπš_πš”_πš™πš˜πšœ constraint
ctrs/differ_from_at_least_k_pos1
Figure 5.99.3. Hypergraph of the reformulation corresponding to the automaton of the πšπš’πšπšπšŽπš›_πšπš›πš˜πš–_𝚊𝚝_πš•πšŽπšŠπšœπš_πš”_πš™πš˜πšœ constraint
ctrs/differ_from_at_least_k_pos2