Global Constraint Catalog: Ccommon

5.75. common

DESCRIPTION

LINKS

GRAPH

Origin

N. Beldiceanu

Constraint

$𝚌𝚘𝚖𝚖𝚘𝚗 (𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1, 𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2)$

Arguments

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

Restrictions

𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1 \geq 0

𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 |

𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2 \geq 0

𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

Purpose

$𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1$ is the number of variables of the collection of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ taking a value in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ .

$𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2$ is the number of variables of the collection of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ taking a value in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ .

Example

(3, 4, 〈1, 9, 1, 5〉, 〈2, 1, 9, 9, 6, 9〉)

The $𝚌𝚘𝚖𝚖𝚘𝚗$ constraint holds since:

Its first argument $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1 = 3$ corresponds to the number of values of the collection $〈 1, 9, 1, 5 〉$ that occur within $〈 2, 1, 9, 9, 6, 9 〉$ .
Its second argument $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2 = 4$ corresponds to the number of values of the collection $〈 2, 1, 9, 9, 6, 9 〉$ that occur within $〈 1, 9, 1, 5 〉$ .

All solutions

Figure 5.75.1 gives all solutions to the following non ground instance of the $𝚌𝚘𝚖𝚖𝚘𝚗$ constraint: $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1 \in [0, 1]$ , $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2 \in [2, 3]$ , $U_{1} \in [1, 2]$ , $U_{2} \in [1, 2]$ , $U_{3} \in [0, 1]$ , $U_{4} \in [5, 6]$ , $V_{1} \in [5, 6]$ , $V_{2} \in [1, 2]$ , $V_{3} \in [0, 1]$ , $𝚌𝚘𝚖𝚖𝚘𝚗$ $(𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1, 𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2, 〈 U_{1}, U_{2}, U_{3}, U_{4} 〉, 〈 V_{1}, V_{2}, V_{3} 〉)$ .

Figure 5.75.1. All solutions corresponding to the non ground example of the $𝚌𝚘𝚖𝚖𝚘𝚗$ constraint of the All solutions slot

Typical

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

𝚛𝚊𝚗𝚐𝚎

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

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

𝚛𝚊𝚗𝚐𝚎

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

Symmetries

Arguments are permutable w.r.t. permutation $(𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1, 𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2)$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2)$ .
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ are permutable.
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ are permutable.
All occurrences of two distinct values in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛$ or $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛$ can be swapped; all occurrences of a value in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛$ or $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛$ can be renamed to any unused value.

Arg. properties

Functional dependency: $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ .
Functional dependency: $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ .

Remark

It was shown in [BessiereHebrardHnichWalsh04a] that, finding out whether the $𝚌𝚘𝚖𝚖𝚘𝚗$ constraint has a solution or not is NP-hard. This was achieved by reduction from 3-SAT.

generalisation: $𝚌𝚘𝚖𝚖𝚘𝚗_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 / 𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝$ ), $𝚌𝚘𝚖𝚖𝚘𝚗_𝚖𝚘𝚍𝚞𝚕𝚘$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 \mod 𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝$ ), $𝚌𝚘𝚖𝚖𝚘𝚗_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 \in 𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ ).

related: $𝚊𝚖𝚘𝚗𝚐_𝚟𝚊𝚛$ , $𝚛𝚘𝚘𝚝𝚜$ .

root concept: $𝚊𝚖𝚘𝚗𝚐$ .

specialisation: $𝚞𝚜𝚎𝚜$ ( $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2$ $=$ $| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 |$ ).

Keywords

complexity: 3-SAT.

constraint arguments: constraint between two collections of variables, pure functional dependency.

constraint type: constraint on the intersection.

final graph structure: acyclic, bipartite, no loop.

modelling: functional dependency.

Arc input(s)

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

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛 = 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛

Graph property(ies)

•

𝐍𝐒𝐎𝐔𝐑𝐂𝐄

= 𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1

•

𝐍𝐒𝐈𝐍𝐊

= 𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2

Graph class

•

𝙰𝙲𝚈𝙲𝙻𝙸𝙲

•

𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴

•

𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

Parts (A) and (B) of Figure 5.75.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 the final graph has only 3 sources and 4 sinks the variables $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1$ and $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2$ are respectively equal to 3 and 4. Note that all the vertices corresponding to the variables that take values 5, 2 or 6 were removed from the final graph since there is no arc for which the associated equality constraint holds.

Figure 5.75.2. Initial and final graph of the $𝚌𝚘𝚖𝚖𝚘𝚗$ constraint


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.75. common

Figure 5.75.1. All solutions corresponding to the non ground example of the 𝚌𝚘𝚖𝚖𝚘𝚗 constraint of the All solutions slot

Figure 5.75.2. Initial and final graph of the 𝚌𝚘𝚖𝚖𝚘𝚗 constraint

Figure 5.75.1. All solutions corresponding to the non ground example of the $𝚌𝚘𝚖𝚖𝚘𝚗$ constraint of the All solutions slot

Figure 5.75.2. Initial and final graph of the $𝚌𝚘𝚖𝚖𝚘𝚗$ constraint