5.2. all_differ_from_at_least_k_pos

DESCRIPTIONLINKSGRAPH
Origin

Inspired by [Frutos97].

Constraint

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

Type
πš…π™΄π™²πšƒπ™ΎπšπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Arguments
π™Ίπš’πš—πš
πš…π™΄π™²πšƒπ™Ύπšπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚟𝚎𝚌-πš…π™΄π™²πšƒπ™Ύπš)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπš,πšŸπšŠπš›)
𝙺β‰₯0
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπšπš‚,𝚟𝚎𝚌)
πšœπšŠπš–πšŽ_πšœπš’πš£πšŽ(πš…π™΄π™²πšƒπ™Ύπšπš‚,𝚟𝚎𝚌)
Purpose

Enforce all pairs of distinct vectors of the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection to differ from at least 𝙺 positions.

Example
2,𝚟𝚎𝚌-2,5,2,0,𝚟𝚎𝚌-3,6,2,1,𝚟𝚎𝚌-3,6,1,0

The πšŠπš•πš•_πšπš’πšπšπšŽπš›_πšπš›πš˜πš–_𝚊𝚝_πš•πšŽπšŠπšœπš_πš”_πš™πš˜πšœ constraint holds since:

  • The first and second vectors differ from 3 positions, which is greater than or equal to 𝙺=2.

  • The first and third vectors differ from 3 positions, which is greater than or equal to 𝙺=2.

  • The second and third vectors differ from 2 positions, which is greater than or equal to 𝙺=2.

Typical
𝙺>0
|πš…π™΄π™²πšƒπ™Ύπšπš‚|>1
Symmetries
  • Items of πš…π™΄π™²πšƒπ™Ύπšπš‚ are permutable.

  • Items of πš…π™΄π™²πšƒπ™Ύπšπš‚.𝚟𝚎𝚌 are permutable (same permutation used).

See also

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

used in graph description: πšπš’πšπšπšŽπš›_πšπš›πš˜πš–_𝚊𝚝_πš•πšŽπšŠπšœπš_πš”_πš™πš˜πšœ.

Keywords

application area: bioinformatics.

characteristic of a constraint: disequality, vector.

constraint type: system of constraints, decomposition.

final graph structure: no loop, symmetric.

Arc input(s)

πš…π™΄π™²πšƒπ™Ύπšπš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈ(β‰ )β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŽπšŒπšπš˜πš›πšœ1,πšŸπšŽπšŒπšπš˜πš›πšœ2)

Arc arity
Arc constraint(s)
πšπš’πšπšπšŽπš›_πšπš›πš˜πš–_𝚊𝚝_πš•πšŽπšŠπšœπš_πš”_πš™πš˜πšœ(𝙺,πšŸπšŽπšŒπšπš˜πš›πšœ1.𝚟𝚎𝚌,πšŸπšŽπšŒπšπš˜πš›πšœ2.𝚟𝚎𝚌)
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš…π™΄π™²πšƒπ™Ύπšπš‚|*|πš…π™΄π™²πšƒπ™Ύπšπš‚|-|πš…π™΄π™²πšƒπ™Ύπšπš‚|

Graph class
β€’ 𝙽𝙾_𝙻𝙾𝙾𝙿
β€’ πš‚πšˆπ™Όπ™Όπ™΄πšƒπšπ™Έπ™²

Graph model

The Arc constraint(s) slot uses the πšπš’πšπšπšŽπš›_πšπš›πš˜πš–_𝚊𝚝_πš•πšŽπšŠπšœπš_πš”_πš™πš˜πšœ constraint defined in this catalogue.

PartsΒ (A) andΒ (B) of FigureΒ 5.2.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. The previous constraint holds since exactly 3Β·(3-1)=6 arc constraints hold.

Figure 5.2.1. Initial and final graph of the πšŠπš•πš•_πšπš’πšπšπšŽπš›_πšπš›πš˜πš–_𝚊𝚝_πš•πšŽπšŠπšœπš_πš”_πš™πš˜πšœ constraint
ctrs/all_differ_from_at_least_k_posActrs/all_differ_from_at_least_k_posB
(a) (b)
Signature

Since we use the πΆπΏπΌπ‘„π‘ˆπΈ(β‰ ) arc generator on the items of the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection, the expression |πš…π™΄π™²πšƒπ™Ύπšπš‚|Β·|πš…π™΄π™²πšƒπ™Ύπšπš‚|-|πš…π™΄π™²πšƒπ™Ύπšπš‚| corresponds to the maximum number of arcs of the final graph. Therefore we can rewrite the graph property 𝐍𝐀𝐑𝐂 = |πš…π™΄π™²πšƒπ™Ύπšπš‚|Β·|πš…π™΄π™²πšƒπ™Ύπšπš‚|-|πš…π™΄π™²πšƒπ™Ύπšπš‚| to 𝐍𝐀𝐑𝐂 β‰₯ |πš…π™΄π™²πšƒπ™Ύπšπš‚|Β·|πš…π™΄π™²πšƒπ™Ύπšπš‚|-|πš…π™΄π™²πšƒπ™Ύπšπš‚|. This leads to simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.