Global Constraint Catalog: Ccommon

5.77. common_modulo

DESCRIPTION

LINKS

GRAPH

Origin

Derived from $𝚌𝚘𝚖𝚖𝚘𝚗$ .

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, 𝚟𝚊𝚛)

𝙼 > 0

Purpose

$𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1$ is the number of variables of the collection of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ taking a value situated in an equivalence class (congruence modulo a fixed number $𝙼$ ) derived from the values assigned to the variables of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ and from $𝙼$ .

$𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2$ is the number of variables of the collection of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ taking a value situated in an equivalence class (congruence modulo a fixed number $𝙼$ ) derived from the values assigned to the variables of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and from $𝙼$ .

Example

(3, 4, 〈0, 4, 0, 8〉, 〈7, 5, 4, 9, 2, 4〉, 5)

In the example, the last argument $𝙼 = 5$ defines the equivalence classes $a \equiv 0 (mod 5)$ , $a \equiv 1 (mod 5)$ , $a \equiv 2 (mod 5)$ , $a \equiv 3 (mod 5)$ , and $a \equiv 4 (mod 5)$ where $a$ is an integer. As a consequence the items of collection $〈 0, 4, 0, 8 〉$ respectively correspond to the equivalence classes $a \equiv 0 (mod 5)$ , $a \equiv 4 (mod 5)$ , $a \equiv 0 (mod 5)$ , and $a \equiv 3 (mod 5)$ . Similarly the items of collection $〈 7, 5, 4, 9, 2, 4 〉$ respectively correspond to the equivalence classes $a \equiv 2 (mod 5)$ , $a \equiv 0 (mod 5)$ , $a \equiv 4 (mod 5)$ , $a \equiv 4 (mod 5)$ , $a \equiv 2 (mod 5)$ , and $a \equiv 4 (mod 5)$ . The $𝚌𝚘𝚖𝚖𝚘𝚗_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint holds since:

Its first argument $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1 = 3$ is the number of equivalence classes associated with the items of collection $〈 0, 4, 0, 8 〉$ that also correspond to equivalence classes associated with $〈 7, 5, 4, 9, 2, 4 〉$ .
Its second argument $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2 = 4$ is the number of equivalence classes associated with the items of collection $〈 7, 5, 4, 9, 2, 4 〉$ that also correspond to equivalence classes associated with $〈 0, 4, 0, 8 〉$ .

Typical

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

𝚛𝚊𝚗𝚐𝚎

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

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

𝚛𝚊𝚗𝚐𝚎

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

𝙼 > 1

𝙼 <

𝚖𝚊𝚡𝚟𝚊𝚕

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

𝙼 <

𝚖𝚊𝚡𝚟𝚊𝚕

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

Symmetries

Arguments are permutable w.r.t. permutation $(𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1, 𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2)$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2)$ $(𝙼)$ .
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ are permutable.
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ are permutable.
An occurrence of a value $u$ of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛$ can be replaced by any other value $v$ such that $v$ is congruent to $u$ modulo $𝙼$ .
An occurrence of a value $u$ of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛$ can be replaced by any other value $v$ such that $v$ is congruent to $u$ modulo $𝙼$ .

Arg. properties

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

See also

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

Keywords

characteristic of a constraint: modulo.

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

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 . 𝚟𝚊𝚛 \mod 𝙼 = 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛 \mod 𝙼

Graph property(ies)

•

𝐍𝐒𝐎𝐔𝐑𝐂𝐄

= 𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1

•

𝐍𝐒𝐈𝐍𝐊

= 𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2

Graph class

•

𝙰𝙲𝚈𝙲𝙻𝙸𝙲

•

𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴

•

𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

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

Figure 5.77.1. Initial and final graph of the $𝚌𝚘𝚖𝚖𝚘𝚗_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.77. common_modulo

Figure 5.77.1. Initial and final graph of the 𝚌𝚘𝚖𝚖𝚘𝚗_𝚖𝚘𝚍𝚞𝚕𝚘 constraint

Figure 5.77.1. Initial and final graph of the $𝚌𝚘𝚖𝚖𝚘𝚗_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint