Global Constraint Catalog: Ck_used_by

5.213. k_used_by_modulo

DESCRIPTION

LINKS

GRAPH

Origin

Derived from $𝚞𝚜𝚎𝚍_𝚋𝚢_𝚖𝚘𝚍𝚞𝚕𝚘$ and from $𝚔_𝚞𝚜𝚎𝚍_𝚋𝚢$ .

Constraint

$𝚔_𝚞𝚜𝚎𝚍_𝚋𝚢_𝚖𝚘𝚍𝚞𝚕𝚘 (𝚂𝙴𝚃𝚂, 𝙼)$

Type

𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)

Arguments

$𝚂𝙴𝚃𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚜𝚎𝚝 - 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$
$𝙼$	$𝚒𝚗𝚝$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚂𝙴𝚃𝚂, 𝚜𝚎𝚝)

| 𝚂𝙴𝚃𝚂 | > 1

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

(𝚂𝙴𝚃𝚂, 𝚜𝚎𝚝)

𝙼 > 0

Purpose

Given $| 𝚂𝙴𝚃𝚂 |$ sets of domain variables, the $𝚔_𝚞𝚜𝚎𝚍_𝚋𝚢_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint forces a $𝚞𝚜𝚎𝚍_𝚋𝚢_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint between each pair of consecutive sets.

Example

(〈𝚜𝚎𝚝 - 〈1, 9, 4, 5, 2, 1〉, 𝚜𝚎𝚝 - 〈7, 1, 2, 5〉, 𝚜𝚎𝚝 - 〈1, 1〉〉, 3)

The $𝚔_𝚞𝚜𝚎𝚍_𝚋𝚢_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint holds since:

The first collection of variables is assigned 1 value in ${0, 3, \dots, 3 \cdot k}$ , 3 values in ${1, 4, \dots, 1 + 3 \cdot k}$ and 2 values in ${2, 5, \dots, 2 + 3 \cdot k}$ , 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 ${0, 3, \dots, 3 \cdot k}$ and 2 values in ${2, 5, \dots, 2 + 3 \cdot k}$ , while the third collection of variables is assigned no more values in the previous three sets of values.

Typical

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

𝙼 > 1

Symmetries

Items of $𝚂𝙴𝚃𝚂$ are permutable.
Items of $𝚂𝙴𝚃𝚂 . 𝚜𝚎𝚝$ are permutable.
An occurrence of a value $u$ of $𝚂𝙴𝚃𝚂 . 𝚜𝚎𝚝 . 𝚟𝚊𝚛$ can be replaced by any other value $v$ such that $v$ is congruent to $u$ modulo $𝙼$ .

Arg. properties

Contractible wrt. $𝚂𝙴𝚃𝚂$ .

implied by: $𝚔_𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘$ .

part of system of constraints: $𝚞𝚜𝚎𝚍_𝚋𝚢_𝚖𝚘𝚍𝚞𝚕𝚘$ .

used in graph description: $𝚞𝚜𝚎𝚍_𝚋𝚢_𝚖𝚘𝚍𝚞𝚕𝚘$ .

Keywords

characteristic of a constraint: modulo, sort based reformulation.

constraint type: system of constraints, decomposition.

modelling: inclusion.

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.213.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.213.1. Initial and final graph of the $𝚔_𝚞𝚜𝚎𝚍_𝚋𝚢_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.213. k_used_by_modulo

Figure 5.213.1. Initial and final graph of the 𝚔_𝚞𝚜𝚎𝚍_𝚋𝚢_𝚖𝚘𝚍𝚞𝚕𝚘 constraint

Figure 5.213.1. Initial and final graph of the $𝚔_𝚞𝚜𝚎𝚍_𝚋𝚢_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint