Global Constraint Catalog: Csame

5.340. same_partition

DESCRIPTION

LINKS

GRAPH

Origin

Derived from $𝚜𝚊𝚖𝚎$ .

Constraint

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

Type

𝚅𝙰𝙻𝚄𝙴𝚂

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

Arguments

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

Restrictions

| 𝚅𝙰𝙻𝚄𝙴𝚂 | \geq 1

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

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

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 | = | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚟𝚊𝚛)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2, 𝚟𝚊𝚛)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

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

Purpose

For each integer $i$ in $[1, | 𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂 |]$ , let $𝑁 1_{i}$ (respectively $𝑁 2_{i}$ ) denote the number of variables of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ (respectively $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ ) that take their value in the $i^{t h}$ partition of the collection $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$ . For all $i$ in $[1, | 𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂 |]$ we have $𝑁 1_{i} = 𝑁 2_{i}$ .

Example

(\begin{matrix} 〈1, 2, 6, 3, 1, 2〉, \\ 〈6, 6, 2, 3, 1, 3〉, \\ 〈𝚙 - 〈1, 3〉, 𝚙 - 〈4〉, 𝚙 - 〈2, 6〉〉 \end{matrix})

The different values of the collection $〈 1, 2, 6, 3, 1, 2 〉$ are respectively associated with the partitions $𝚙 - 〈 1, 3 〉$ , $𝚙 - 〈 2, 6 〉$ , $𝚙 - 〈 2, 6 〉$ , $𝚙 - 〈 1, 3 〉$ , $𝚙 - 〈 1, 3 〉$ , and $𝚙 - 〈 2, 6 〉$ . Therefore partitions $𝚙 - 〈 1, 3 〉$ and $𝚙 - 〈 2, 6 〉$ are respectively used 3 and 3 times. Similarly, the different values of the collection $〈 6, 6, 2, 3, 1, 3 〉$ are respectively associated with the partitions $𝚙 - 〈 2, 6 〉$ , $𝚙 - 〈 2, 6 〉$ , $𝚙 - 〈 2, 6 〉$ , $𝚙 - 〈 1, 3 〉$ , $𝚙 - 〈 1, 3 〉$ , and $𝚙 - 〈 1, 3 〉$ . As before partitions $𝚙 - 〈 1, 3 〉$ and $𝚙 - 〈 2, 6 〉$ are respectively used 3 and 3 times. Consequently the $𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint holds. Figure 5.340.1 illustrates this correspondence.

Figure 5.340.1. Illustration of the correspondence between the items of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ collections of the Example slot

Typical

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛) > 1

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛) > 1

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 | > | 𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂 |

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 | > | 𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂 |

Symmetries

Arguments are permutable w.r.t. permutation $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2)$ $(𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂)$ .
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ are permutable.
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ are permutable.
Items of $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$ are permutable.
Items of $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂 . 𝚙$ are permutable.
An occurrence of a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ can be replaced by any other value that also belongs to the same partition of $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$ .

Arg. properties

Aggregate: $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 (𝚞𝚗𝚒𝚘𝚗)$ , $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 (𝚞𝚗𝚒𝚘𝚗)$ , $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂 (𝚒𝚍)$ .

Used in

$𝚔_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ .

See also

implies: $𝚞𝚜𝚎𝚍_𝚋𝚢_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ .

soft variant: $𝚜𝚘𝚏𝚝_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗_𝚟𝚊𝚛$ (variable-based violation measure).

specialisation: $𝚜𝚊𝚖𝚎$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 \in 𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ ).

system of constraints: $𝚔_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ .

used in graph description: $𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ .

Keywords

characteristic of a constraint: sort based reformulation, partition.

combinatorial object: permutation.

constraint arguments: constraint between two collections of variables.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗

(𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛, 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛, 𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂)

Graph property(ies)

• for all connected components:

𝐍𝐒𝐎𝐔𝐑𝐂𝐄

=

𝐍𝐒𝐈𝐍𝐊

•

𝐍𝐒𝐎𝐔𝐑𝐂𝐄

= | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 |

•

𝐍𝐒𝐈𝐍𝐊

= | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 |

Graph model

Parts (A) and (B) of Figure 5.340.2 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐍𝐒𝐎𝐔𝐑𝐂𝐄$ and $𝐍𝐒𝐈𝐍𝐊$ graph properties, the source and sink vertices of the final graph are stressed with a double circle. Since there is a constraint on each connected component of the final graph we also show the different connected components. Each of them corresponds to an equivalence class according to the arc constraint. The $𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint holds since:

Each connected component of the final graph has the same number of sources and of sinks.
The number of sources of the final graph is equal to $| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 |$ .
The number of sinks of the final graph is equal to $| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 |$ .

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

(a)

(b)

Signature

Since the initial graph contains only sources and sinks, and since isolated vertices are eliminated from the final graph, we make the following observations:

Sources of the initial graph cannot become sinks of the final graph,
Sinks of the initial graph cannot become sources of the final graph.

From the previous observations and since we use the $𝑃𝑅𝑂𝐷𝑈𝐶𝑇$ arc generator on the collections $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ , we have that the maximum number of sources and sinks of the final graph is respectively equal to $| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 |$ and $| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 |$ . Therefore we can rewrite $𝐍𝐒𝐎𝐔𝐑𝐂𝐄 = | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 |$ to $𝐍𝐒𝐎𝐔𝐑𝐂𝐄 \geq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 |$ and simplify $\underset{̲}{\bar{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}}$ to $\bar{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}$ . In a similar way, we can rewrite $𝐍𝐒𝐈𝐍𝐊 = | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 |$ to $𝐍𝐒𝐈𝐍𝐊 \geq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 |$ and simplify $\underset{̲}{\bar{𝐍𝐒𝐈𝐍𝐊}}$ to $\bar{𝐍𝐒𝐈𝐍𝐊}$ .

Global Constraint Catalog

5. Global Constraint Catalogue

5.340. same_partition

Figure 5.340.1. Illustration of the correspondence between the items of the 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂1 and of the 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂2 collections of the Example slot

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

Figure 5.340.1. Illustration of the correspondence between the items of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ collections of the Example slot

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