Global Constraint Catalog: Ck_used_by

5.214. k_used_by_partition

DESCRIPTION

LINKS

GRAPH

Origin

Derived from $𝚞𝚜𝚎𝚍_𝚋𝚢_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ and from $𝚔_𝚞𝚜𝚎𝚍_𝚋𝚢$ .

Constraint

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

Types

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

Arguments

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

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | \geq 1

| 𝚅𝙰𝙻𝚄𝙴𝚂 | \geq 1

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚂𝙴𝚃𝚂, 𝚜𝚎𝚝)

| 𝚂𝙴𝚃𝚂 | > 1

𝚗𝚘𝚗_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚒𝚣𝚎

(𝚂𝙴𝚃𝚂, 𝚜𝚎𝚝)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

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

Purpose

Given $| 𝚂𝙴𝚃𝚂 |$ sets of domain variables, the $𝚔_𝚞𝚜𝚎𝚍_𝚋𝚢_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint forces a $𝚞𝚜𝚎𝚍_𝚋𝚢_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint between each pair of consecutive sets.

Example

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

The $𝚔_𝚞𝚜𝚎𝚍_𝚋𝚢_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint holds since:

The first collection of variables is assigned 3 values in ${1, 3}$ , 0 value in ${4}$ and 2 values in ${2, 6}$ , while the second collection of variables is assigned no more values in the previous three sets of values.
The second collection of variables is assigned 2 values in ${1, 3}$ , 0 value in ${4}$ and 2 values in ${2, 6}$ , while the third collection of variables is assigned no more values in the previous three sets of values.

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 $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$ .

Arg. properties

Contractible wrt. $𝚂𝙴𝚃𝚂$ .

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

part of system of constraints: $𝚞𝚜𝚎𝚍_𝚋𝚢_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ .

used in graph description: $𝚞𝚜𝚎𝚍_𝚋𝚢_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ .

Keywords

characteristic of a constraint: partition, sort based reformulation.

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.214.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.214.1. Initial and final graph of the $𝚔_𝚞𝚜𝚎𝚍_𝚋𝚢_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.214. k_used_by_partition

Figure 5.214.1. Initial and final graph of the 𝚔_𝚞𝚜𝚎𝚍_𝚋𝚢_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗 constraint

Figure 5.214.1. Initial and final graph of the $𝚔_𝚞𝚜𝚎𝚍_𝚋𝚢_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ constraint