## 5.123. disjoint

Origin
Constraint

$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}\right)$

Arguments
 $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$ $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$
Restrictions
 $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1},\mathrm{\pi \pi \pi }\right)$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2},\mathrm{\pi \pi \pi }\right)$
Purpose

Each variable of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ should take a value that is distinct from all the values assigned to the variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$.

Example
$\left(β©1,9,1,5βͺ,β©2,7,7,0,6,8βͺ\right)$

In this example, values $1,5,9$ are used by the variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ and values $0,2,6,7,8$ by the variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$. Since there is no intersection between the two previous sets of values the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ constraint holds.

All solutions

FigureΒ 5.123.1 gives all solutions to the following non ground instance of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ constraint: ${U}_{1}\beta \left[0..2\right]$, ${U}_{2}\beta \left[1..2\right]$, ${U}_{3}\beta \left[1..2\right]$, ${V}_{1}\beta \left[0..1\right]$, ${V}_{2}\beta \left[1..2\right]$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\beta ©{U}_{1},{U}_{2},{U}_{3}\beta ͺ,\beta ©{V}_{1},{V}_{2}\beta ͺ\right)$.

Typical
 $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}|>1$ $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}|>1$
Symmetries
• Arguments are permutable w.r.t. permutation $\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}\right)$.

• Items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ are permutable.

• Items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$ are permutable.

• An occurrence of a value of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}.\mathrm{\pi \pi \pi }$ can be replaced by any value of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}.\mathrm{\pi \pi \pi }$.

• An occurrence of a value of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}.\mathrm{\pi \pi \pi }$ can be replaced by any value of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}.\mathrm{\pi \pi \pi }$.

• All occurrences of two distinct values in $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}.\mathrm{\pi \pi \pi }$ or $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}.\mathrm{\pi \pi \pi }$ can be swapped; all occurrences of a value in $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}.\mathrm{\pi \pi \pi }$ or $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}.\mathrm{\pi \pi \pi }$ can be renamed to any unused value.

Arg. properties
• Contractible wrt. $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$.

• Contractible wrt. $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$.

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 $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint. The $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ constraint can bee seen as a special case of the $\mathrm{\pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi ½\pi ²\pi Ύ\pi Ό\pi Ό\pi Ύ\pi ½}\mathtt{1},\mathrm{\pi ½\pi ²\pi Ύ\pi Ό\pi Ό\pi Ύ\pi ½}\mathtt{2},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}\right)$ constraint where $\mathrm{\pi ½\pi ²\pi Ύ\pi Ό\pi Ό\pi Ύ\pi ½}\mathtt{1}$ and $\mathrm{\pi ½\pi ²\pi Ύ\pi Ό\pi Ό\pi Ύ\pi ½}\mathtt{2}$ are both set to 0.

MiniZinc (http://www.minizinc.org/) has a $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ constraint between two set variables rather than between two collections of variables.

Algorithm

Let us note:

• ${n}_{1}$ the minimum number of distinct values taken by the variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$.

• ${n}_{2}$ the minimum number of distinct values taken by the variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$.

• ${n}_{12}$ the maximum number of distinct values taken by the union of the variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ and $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$.

One invariant to maintain for the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ constraint is ${n}_{1}+{n}_{2}\beta €{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

generalisation: $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi }$).

Keywords
Arc input(s)

$\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$

Arc generator
$\mathrm{\pi \pi  \pi \pi ·\pi \pi Ά\pi }$$\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1},\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi }=\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi }$
Graph property(ies)
$\mathrm{\pi \pi \pi \pi }$$=0$

Graph model

$\mathrm{\pi \pi  \pi \pi ·\pi \pi Ά\pi }$ is used in order to generate the arcs of the graph between all variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ and all variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$. Since we use the graph property $\mathrm{\pi \pi \pi \pi }$ $=$ 0 the final graph will be empty. FigureΒ 5.123.2 shows the initial graph associated with the Example slot. Since we use the $\mathrm{\pi \pi \pi \pi }$ $=$ 0 graph property the final graph is empty.

Signature

Since 0 is the smallest number of arcs of the final graph we can rewrite $\mathrm{\pi \pi \pi \pi }$ $=$ 0 to $\mathrm{\pi \pi \pi \pi }$ $\beta €$ 0. This leads to simplify $\underset{Μ²}{\stackrel{Β―}{\mathrm{\pi \pi \pi \pi }}}$ to $\underset{Μ²}{\mathrm{\pi \pi \pi \pi }}$.

Automaton

FigureΒ 5.123.3 depicts the automaton associated with the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ constraint. To each variable $\mathrm{\pi  \pi °\pi }{\mathtt{1}}_{i}$ of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ corresponds a signature variable ${S}_{i}$ that is equal to 0. To each variable $\mathrm{\pi  \pi °\pi }{\mathtt{2}}_{i}$ of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$ corresponds a signature variable ${S}_{i+|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}|}$ that is equal to 1.