Global Constraint Catalog: Ck_same

5.181. k_same_partition

DESCRIPTION

LINKS

GRAPH

Origin

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

Constraint

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

Types

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝚅𝙰𝙻𝚄𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚕 - 𝚒𝚗𝚝)$

Arguments

$𝚂𝙴𝚃𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚜𝚎𝚝 - 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$
$𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚙 - 𝚅𝙰𝙻𝚄𝙴𝚂)$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

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

| 𝚅𝙰𝙻𝚄𝙴𝚂 | \geq 1

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚂𝙴𝚃𝚂, 𝚜𝚎𝚝)

| 𝚂𝙴𝚃𝚂 | > 1

𝚜𝚊𝚖𝚎_𝚜𝚒𝚣𝚎

(𝚂𝙴𝚃𝚂, 𝚜𝚎𝚝)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

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

Purpose

Given a collection of $| 𝚂𝙴𝚃𝚂 |$ sets, each containing the same number of domain variables, the $𝚔_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint enforces a $𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint between each pair of consecutive sets.

Example

(\begin{matrix} 〈\begin{matrix} 𝚜𝚎𝚝 - 〈\begin{matrix} 𝚟𝚊𝚛 - 1, \\ 𝚟𝚊𝚛 - 2, \\ 𝚟𝚊𝚛 - 6, \\ 𝚟𝚊𝚛 - 3, \\ 𝚟𝚊𝚛 - 1, \\ 𝚟𝚊𝚛 - 2 \end{matrix}〉, \\ 𝚜𝚎𝚝 - 〈\begin{matrix} 𝚟𝚊𝚛 - 6, \\ 𝚟𝚊𝚛 - 6, \\ 𝚟𝚊𝚛 - 2, \\ 𝚟𝚊𝚛 - 3, \\ 𝚟𝚊𝚛 - 1, \\ 𝚟𝚊𝚛 - 3 \end{matrix}〉, \\ 𝚜𝚎𝚝 - 〈\begin{matrix} 𝚟𝚊𝚛 - 2, \\ 𝚟𝚊𝚛 - 2, \\ 𝚟𝚊𝚛 - 2, \\ 𝚟𝚊𝚛 - 1, \\ 𝚟𝚊𝚛 - 1, \\ 𝚟𝚊𝚛 - 1 \end{matrix}〉 \end{matrix}〉, \\ 〈\begin{matrix} 𝚙 - 〈1, 3〉, \\ 𝚙 - 〈4〉, \\ 𝚙 - 〈2, 6〉 \end{matrix}〉 \end{matrix})

The first argument $𝚂𝙴𝚃𝚂$ of the $𝚔_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint corresponds to 3 collections of variables, while the second argument $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$ defines the 3 sets of values ${1, 3}$ , ${4}$ and ${2, 6}$ . The $𝚔_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint holds since:

The first and second collections of variables are assigned 3 values in the ${1, 3}$ as well as 3 values in ${2, 6}$ .
The second and third collections of variables are also assigned 3 values in the ${1, 3}$ as well as 3 values in ${2, 6}$ .

Typical

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

Symmetries

Items of $𝚂𝙴𝚃𝚂$ are permutable.
Items of $𝚂𝙴𝚃𝚂 . 𝚜𝚎𝚝$ 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 $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$ .

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

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

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

Keywords

characteristic of a constraint: partition.

combinatorial object: permutation.

constraint type: system of constraints, decomposition.

Arc input(s)

$𝚂𝙴𝚃𝚂$

Arc generator

𝑃𝐴𝑇𝐻

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚜𝚎𝚝 1, 𝚜𝚎𝚝 2)

Arc arity

Arc constraint(s)

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

(𝚜𝚎𝚝 1 . 𝚜𝚎𝚝, 𝚜𝚎𝚝 2 . 𝚜𝚎𝚝, 𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂)

Graph property(ies)

𝐍𝐀𝐑𝐂

= | 𝚂𝙴𝚃𝚂 | - 1

Graph model

Parts (A) and (B) of Figure 5.181.1 respectively show the initial and final graph associated with the Example slot. To each vertex corresponds a collection of variables, while to each arc corresponds a $𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint.

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


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.181. k_same_partition

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

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

Global Constraint Catalog

5. Global Constraint Catalogue

5.181. k_same_partition

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

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

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