Global Constraint Catalog: Cin_same

5.182. in_same_partition

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Used for defining several entries of this catalog.

Constraint

$𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗 (𝚅𝙰𝚁 1, 𝚅𝙰𝚁 2, 𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂)$

Type

𝚅𝙰𝙻𝚄𝙴𝚂

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚕 - 𝚒𝚗𝚝)

Arguments

$𝚅𝙰𝚁 1$	$𝚍𝚟𝚊𝚛$
$𝚅𝙰𝚁 2$	$𝚍𝚟𝚊𝚛$
$𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚙 - 𝚅𝙰𝙻𝚄𝙴𝚂)$

Restrictions

| 𝚅𝙰𝙻𝚄𝙴𝚂 | \geq 1

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝙻𝚄𝙴𝚂, 𝚟𝚊𝚕)

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

(𝚅𝙰𝙻𝚄𝙴𝚂, 𝚟𝚊𝚕)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂, 𝚙)

| 𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂 | \geq 2

Purpose

Enforce $𝚅𝙰𝚁 1$ and $𝚅𝙰𝚁 2$ to be respectively assigned to values $v_{1}$ and $v_{2}$ that both belong to a same partition of the collection $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$ .

Example

(6, 2, 〈𝚙 - 〈1, 3〉, 𝚙 - 〈4〉, 𝚙 - 〈2, 6〉〉)

The $𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint holds since its first and second arguments $𝚅𝙰𝚁 1 = 6$ and $𝚅𝙰𝚁 2 = 2$ both belong to the third partition $〈 2, 6 〉$ of its third argument $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$ .

Typical

𝚅𝙰𝚁 1 \neq 𝚅𝙰𝚁 2

Symmetries

Arguments are permutable w.r.t. permutation $(𝚅𝙰𝚁 1, 𝚅𝙰𝚁 2)$ $(𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂)$ .
Items of $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$ are permutable.
Items of $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂 . 𝚙$ are permutable.

Arg. properties

Extensible wrt. $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$ .

Used in

used in graph description: $𝚒𝚗$ .

Keywords

characteristic of a constraint: partition, automaton, automaton without counters, reified automaton constraint, derived collection.

constraint arguments: binary constraint.

constraint network structure: centered cyclic(2) constraint network(1).

constraint type: value constraint.

filtering: arc-consistency.

Derived Collection

𝚌𝚘𝚕 (\begin{matrix} 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛), \\ 𝚒𝚝𝚎𝚖 (𝚟𝚊𝚛 - 𝚅𝙰𝚁 1), 𝚒𝚝𝚎𝚖 (𝚟𝚊𝚛 - 𝚅𝙰𝚁 2)] \end{matrix})

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜, 𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗𝚜)

Arc arity

Arc constraint(s)

𝚒𝚗

(𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚟𝚊𝚛, 𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗𝚜 . 𝚙)

Graph property(ies)

•

𝐍𝐒𝐎𝐔𝐑𝐂𝐄

= 2

•

𝐍𝐒𝐈𝐍𝐊

= 1

Graph model

$𝚅𝙰𝚁 1$ and $𝚅𝙰𝚁 2$ are put together in the derived collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ . Since both $𝚅𝙰𝚁 1$ and $𝚅𝙰𝚁 2$ should take their value in one of the partition depicted by the $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$ collection, the final graph should have two sources corresponding respectively to $𝚅𝙰𝚁 1$ and $𝚅𝙰𝚁 2$ . Since two, possibly distinct, values should be assigned to $𝚅𝙰𝚁 1$ and $𝚅𝙰𝚁 2$ and since these values belong to the same partition $p$ the final graph should only have one sink. This sink corresponds in fact to partition $p$ .

Parts (A) and (B) of Figure 5.182.1 respectively show the initial and final graph associated with the Example slot. Since we both use the $𝐍𝐒𝐎𝐔𝐑𝐂𝐄$ and $𝐍𝐒𝐈𝐍𝐊$ graph properties, the source and sink vertices of the final graph are shown with a double circle.

Figure 5.182.1. Initial and final graph of the $𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint


(a)	(b)

Signature

Note that the sinks of the initial graph cannot become sources of the final graph since isolated vertices are eliminated from the final graph. Since the final graph contains two sources it also includes one arc between a source and a sink. Therefore the minimum number of sinks of the final graph is equal to one. So we can rewrite $𝐍𝐒𝐈𝐍𝐊 = 1$ to $𝐍𝐒𝐈𝐍𝐊 \geq 1$ and simplify $\underset{̲}{\bar{𝐍𝐒𝐈𝐍𝐊}}$ to $\bar{𝐍𝐒𝐈𝐍𝐊}$ .

Automaton: Figure 5.182.2 depicts the automaton associated with the $𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint. Let ${𝚅𝙰𝙻𝚄𝙴𝚂}_{i}$ be the $𝚙$ attribute of the $i^{t h}$ item of the $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$ collection. To each triple $(𝚅𝙰𝚁 1, 𝚅𝙰𝚁 2, {𝚅𝙰𝙻𝚄𝙴𝚂}_{i})$ corresponds a 0-1 signature variable $S_{i}$ as well as the following signature constraint: $((𝚅𝙰𝚁 1 \in {𝚅𝙰𝙻𝚄𝙴𝚂}_{i}) \land (𝚅𝙰𝚁 2 \in {𝚅𝙰𝙻𝚄𝙴𝚂}_{i})) \Leftrightarrow S_{i}$ .

Figure 5.182.2. Automaton of the $𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint

Figure 5.182.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.182. in_same_partition

Figure 5.182.1. Initial and final graph of the $𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint

Figure 5.182.2. Automaton of the $𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint

Figure 5.182.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.182. in_same_partition

Figure 5.182.1. Initial and final graph of the 𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗 constraint

Figure 5.182.2. Automaton of the 𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗 constraint

Figure 5.182.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗 constraint

Figure 5.182.1. Initial and final graph of the $𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint

Figure 5.182.2. Automaton of the $𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint

Figure 5.182.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint