5.105. disjoint

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

Constraint

πšπš’πšœπš“πš˜πš’πš—πš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2)

Arguments
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2,πšŸπšŠπš›)
Purpose

Each variable of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 should take a value that is distinct from all the values assigned to the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.

Example
1,9,1,5,πšŸπšŠπš›-2,πšŸπšŠπš›-7,πšŸπšŠπš›-7,πšŸπšŠπš›-0,πšŸπšŠπš›-6,πšŸπšŠπš›-8

In this example, values 1,5,9 are used by the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and values 0,2,6,7,8 by the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2. Since there is no intersection between the two previous sets of values the πšπš’πšœπš“πš˜πš’πš—πš constraint holds.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|>1
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|>1
Symmetries
  • Arguments are permutable w.r.t. permutation (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2).

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

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

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.πšŸπšŠπš› can be replaced by any value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.πšŸπšŠπš›.

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.πšŸπšŠπš› can be replaced by any value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.πšŸπšŠπš›.

  • All occurrences of two distinct values in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.πšŸπšŠπš› or πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.πšŸπšŠπš› can be swapped; all occurrences of a value in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.πšŸπšŠπš› or πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.πšŸπšŠπš› can be renamed to any unused value.

Remark

Despite the fact that this is not an uncommon constraint, it can not be modelled in a compact way neither with a disequality constraint (i.e.,Β two given variables have to take distinct values) nor with the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint. The πšπš’πšœπš“πš˜πš’πš—πš constraint can bee seen as a special case of the πšŒπš˜πš–πš–πš˜πš—(𝙽𝙲𝙾𝙼𝙼𝙾𝙽1,𝙽𝙲𝙾𝙼𝙼𝙾𝙽2,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2) constraint where 𝙽𝙲𝙾𝙼𝙼𝙾𝙽1 and 𝙽𝙲𝙾𝙼𝙼𝙾𝙽2 are both set to 0.

Algorithm

Let us note:

  • n 1 the minimum number of distinct values taken by the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.

  • n 2 the minimum number of distinct values taken by the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.

  • n 12 the maximum number of distinct values taken by the union of the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.

One invariant to maintain for the πšπš’πšœπš“πš˜πš’πš—πš constraint is n 1 +n 2 ≀n 12 . A lower bound of n 1 and n 2 can be obtained by using the algorithms provided in [Beldiceanu01], [BeldiceanuCarlssonThiel02]. An exact upper bound of n 12 can be computed by using a bipartite matching algorithm.

Used in

πš”_πšπš’πšœπš“πš˜πš’πš—πš.

See also

generalisation: πšπš’πšœπš“πš˜πš’πš—πš_πšπšŠπšœπš”πšœΒ (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšπšŠπšœπš”).

implies: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš˜πš—_πš’πš—πšπšŽπš›πšœπšŽπšŒπšπš’πš˜πš—, πš•πšŽπš‘_πšπš’πšπšπšŽπš›πšŽπš—πš.

system of constraints: πš”_πšπš’πšœπš“πš˜πš’πš—πš.

Keywords

characteristic of a constraint: disequality, automaton, automaton with array of counters.

constraint type: value constraint.

filtering: bipartite matching.

modelling: empty intersection.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
𝐍𝐀𝐑𝐂=0

Graph model

π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡ is used in order to generate the arcs of the graph between all variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and all variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2. Since we use the graph property 𝐍𝐀𝐑𝐂 = 0 the final graph will be empty. FigureΒ 5.105.1 shows the initial graph associated with the Example slot. Since we use the 𝐍𝐀𝐑𝐂 = 0 graph property the final graph is empty.

Figure 5.105.1. Initial graph of the πšπš’πšœπš“πš˜πš’πš—πš constraint (the final graph is empty)
ctrs/disjointA
Signature

Since 0 is the smallest number of arcs of the final graph we can rewrite 𝐍𝐀𝐑𝐂 = 0 to 𝐍𝐀𝐑𝐂 ≀ 0. This leads to simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Μ².

Automaton

FigureΒ 5.105.2 depicts the automaton associated with the πšπš’πšœπš“πš˜πš’πš—πš constraint. To each variable πš…π™°πš1 i of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 corresponds a signature variable πš‚ i that is equal to 0. To each variable πš…π™°πš2 i of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 corresponds a signature variable πš‚ i+|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1| that is equal to 1.

Figure 5.105.2. Automaton of the πšπš’πšœπš“πš˜πš’πš—πš constraint
ctrs/disjoint1