Global Constraint Catalog: Csame_and_global

5.335. same_and_global_cardinality

DESCRIPTION

LINKS

GRAPH

Origin

Conjoin $𝚜𝚊𝚖𝚎$ and $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$

Constraint

$𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2, 𝚅𝙰𝙻𝚄𝙴𝚂)$

Synonyms

$𝚜𝚐𝚌𝚌$ , $𝚜𝚊𝚖𝚎_𝚐𝚌𝚌$ , $𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚌𝚌$ , $𝚜𝚠𝚌$ , $𝚜𝚊𝚖𝚎_𝚠𝚒𝚝𝚑_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚒𝚎𝚜$ .

Arguments

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

Restrictions

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝙻𝚄𝙴𝚂, [𝚟𝚊𝚕, 𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎])

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

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

𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎 \geq 0

𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 |

Purpose

The variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ collection correspond to the variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ collection according to a permutation. In addition, each value $𝚅𝙰𝙻𝚄𝙴𝚂 [i] . 𝚟𝚊𝚕$ (with $i \in [1, | 𝚅𝙰𝙻𝚄𝙴𝚂 |]$ ) should be taken by exactly $𝚅𝙰𝙻𝚄𝙴𝚂 [i] . 𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎$ variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ collection. Finally, each variable of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ should be assigned a value of $𝚅𝙰𝙻𝚄𝙴𝚂 [i] . 𝚟𝚊𝚕$ (with $i \in [1, | 𝚅𝙰𝙻𝚄𝙴𝚂 |]$ ).

Example

(\begin{matrix} 〈1, 9, 1, 5, 2, 1〉, \\ 〈9, 1, 1, 1, 2, 5〉, \\ 〈\begin{matrix} 𝚟𝚊𝚕 - 1 & 𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎 - 3, \\ 𝚟𝚊𝚕 - 2 & 𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎 - 1, \\ 𝚟𝚊𝚕 - 5 & 𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎 - 1, \\ 𝚟𝚊𝚕 - 7 & 𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎 - 0, \\ 𝚟𝚊𝚕 - 9 & 𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎 - 1 \end{matrix}〉 \end{matrix})

The $𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ constraint holds since:

The values 1, 9, 1, 5, 2, 1 assigned to $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ correspond to a permutation of the values 9, 1, 1, 1, 2, 5 assigned to $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ .
The values 1, 2, 5, 7 and 6 are respectively used 3, 1, 1, 0 and 1 times.

Typical

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

𝚛𝚊𝚗𝚐𝚎

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

𝚛𝚊𝚗𝚐𝚎

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

| 𝚅𝙰𝙻𝚄𝙴𝚂 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎) > 1

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

Symmetries

Arguments are permutable w.r.t. permutation $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2)$ $(𝚅𝙰𝙻𝚄𝙴𝚂)$ .
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ are permutable.
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ are permutable.
Items of $𝚅𝙰𝙻𝚄𝙴𝚂$ are permutable.
An occurrence of a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛$ or $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛$ that does not belong to $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ can be replaced by any other value that also does not belong to $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ .
All occurrences of two distinct values in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛$ , $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛$ or $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ can be swapped; all occurrences of a value in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛$ , $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛$ or $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ can be renamed to any unused value.

Arg. properties

Contractible wrt. $𝚅𝙰𝙻𝚄𝙴𝚂$ .

Usage

See the $𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙$ constraint.

Algorithm

The filtering algorithm presented in [BeldiceanuKatrielThiel05b] can be reused for pruning the variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ collection. This algorithm does not restrict the $𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎$ variables of the $𝚅𝙰𝙻𝚄𝙴𝚂$ collection.

specialisation: $𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ replaced by $𝚏𝚒𝚡𝚎𝚍$ $𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ ).

Keywords

application area: assignment.

combinatorial object: permutation, multiset.

constraint arguments: constraint between two collections of variables.

constraint type: value constraint.

filtering: flow.

modelling: equality between multisets.

problems: demand profile.

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 |

For all items of $𝚅𝙰𝙻𝚄𝙴𝚂$ :

Arc input(s)

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

Arc generator

𝑆𝐸𝐿𝐹

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

Arc arity

Arc constraint(s)

𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚟𝚊𝚛 = 𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕

Graph property(ies)

𝐍𝐕𝐄𝐑𝐓𝐄𝐗

= 𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎

Graph model

Parts (A) and (B) of Figure 5.335.1 respectively show the initial and final graph associated with the first graph constraint of 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.

Figure 5.335.1. Initial and final graph of the $𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ constraint

(a)

(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.335. same_and_global_cardinality

Figure 5.335.1. Initial and final graph of the 𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢 constraint

Figure 5.335.1. Initial and final graph of the $𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ constraint