Global Constraint Catalog: Cdisjoint

5.105. disjoint

DESCRIPTION

LINKS

GRAPH

AUTOMATON

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

(\begin{matrix} 〈1, 9, 1, 5〉, \\ 〈\begin{matrix} 𝚟𝚊𝚛 - 2, \\ 𝚟𝚊𝚛 - 7, \\ 𝚟𝚊𝚛 - 7, \\ 𝚟𝚊𝚛 - 0, \\ 𝚟𝚊𝚛 - 6, \\ 𝚟𝚊𝚛 - 8 \end{matrix}〉 \end{matrix})

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} \leq 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: $𝑃𝑅𝑂𝐷𝑈𝐶𝑇$ $\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 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)
Signature: Since 0 is the smallest number of arcs of the final graph we can rewrite $𝐍𝐀𝐑𝐂$ $=$ 0 to $𝐍𝐀𝐑𝐂$ $\leq$ 0. This leads to simplify $\underset{̲}{\bar{𝐍𝐀𝐑𝐂}}$ to $\underset{̲}{𝐍𝐀𝐑𝐂}$ .

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

Global Constraint Catalog

5. Global Constraint Catalogue

5.105. disjoint

Figure 5.105.1. Initial graph of the $𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝$ constraint (the final graph is empty)

Figure 5.105.2. Automaton of the $𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝$ constraint

W3C: XHTML - last update: 2010-12-6. SD.

Global Constraint Catalog

5. Global Constraint Catalogue

5.105. disjoint

Figure 5.105.1. Initial graph of the 𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝 constraint (the final graph is empty)

Figure 5.105.2. Automaton of the 𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝 constraint

W3C: XHTML - last update: 2010-12-6. SD.

Figure 5.105.1. Initial graph of the $𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝$ constraint (the final graph is empty)

Figure 5.105.2. Automaton of the $𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝$ constraint