Global Constraint Catalog: Cperiod

5.319. period

DESCRIPTION

LINKS

Origin

N. Beldiceanu

Constraint

$𝚙𝚎𝚛𝚒𝚘𝚍 (𝙿𝙴𝚁𝙸𝙾𝙳, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝙲𝚃𝚁)$

Arguments

$𝙿𝙴𝚁𝙸𝙾𝙳$	$𝚍𝚟𝚊𝚛$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝙲𝚃𝚁$	$𝚊𝚝𝚘𝚖$

Restrictions

𝙿𝙴𝚁𝙸𝙾𝙳 \geq 1

𝙿𝙴𝚁𝙸𝙾𝙳 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝙲𝚃𝚁 \in [=, \neq, <, \geq, >, \leq]

Purpose

Let us note $V_{0}, V_{1}, \dots, V_{m - 1}$ the variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection. $𝙿𝙴𝚁𝙸𝙾𝙳$ is the period of the sequence $V_{0} V_{1} \dots V_{m - 1}$ according to constraint $𝙲𝚃𝚁$ . This means that $𝙿𝙴𝚁𝙸𝙾𝙳$ is the smallest natural number such that $V_{i} 𝙲𝚃𝚁 V_{i + 𝙿𝙴𝚁𝙸𝙾𝙳}$ holds for all $i \in 0, 1, \dots, m - 𝙿𝙴𝚁𝙸𝙾𝙳 - 1$ .

Example

(3, 〈1, 1, 4, 1, 1, 4, 1, 1〉, =)

The $𝚙𝚎𝚛𝚒𝚘𝚍$ constraint holds since, as depicted by Figure 5.319.1, its first argument $𝙿𝙴𝚁𝙸𝙾𝙳 = 3$ is equal (i.e., since $𝙲𝚃𝚁$ is set to $=$ ) to the period of the sequence $11411411$ .

Figure 5.319.1. A sequence of period 3

Typical

𝙿𝙴𝚁𝙸𝙾𝙳 > 1

𝙿𝙴𝚁𝙸𝙾𝙳 < | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

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

𝚛𝚊𝚗𝚐𝚎

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

𝙲𝚃𝚁 \in [=]

Symmetries

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ can be reversed.
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ can be shifted.
All occurrences of two distinct values of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ can be swapped; all occurrences of a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ can be renamed to any unused value.

Arg. properties

Functional dependency: $𝙿𝙴𝚁𝙸𝙾𝙳$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ and $𝙲𝚃𝚁$ .
Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙲𝚃𝚁 \in [=]$ and $𝙿𝙴𝚁𝙸𝙾𝙳 = 1$ .
Prefix-contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .
Suffix-contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Algorithm

When $𝙲𝚃𝚁$ corresponds to the equality constraint, a potentially incomplete filtering algorithm based on 13 deductions rules is described in [BeldiceanuPoder04]. The generalisation of these rules to the case where $𝙲𝚃𝚁$ is not the equality constraint is discussed.

See also

generalisation: $𝚙𝚎𝚛𝚒𝚘𝚍_𝚟𝚎𝚌𝚝𝚘𝚛𝚜$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ replaced by vector).

implies: $𝚙𝚎𝚛𝚒𝚘𝚍_𝚎𝚡𝚌𝚎𝚙𝚝_0$ .

soft variant: $𝚙𝚎𝚛𝚒𝚘𝚍_𝚎𝚡𝚌𝚎𝚙𝚝_0$ (value 0 can match any other value).

Keywords

combinatorial object: periodic, sequence.

constraint arguments: pure functional dependency.

constraint type: predefined constraint, timetabling constraint, scheduling constraint.

filtering: border.

modelling: functional dependency.

Global Constraint Catalog

5. Global Constraint Catalogue

5.319. period

Figure 5.319.1. A sequence of period 3