Global Constraint Catalog: Cperiod_except

5.320. period_except_0

DESCRIPTION

LINKS

Origin

Constraint

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

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 + 𝙿𝙴𝚁𝙸𝙾𝙳} \lor V_{i} = 0 \lor V_{i + 𝙿𝙴𝚁𝙸𝙾𝙳} = 0$ holds for all $i \in 0, 1, \dots, m - 𝙿𝙴𝚁𝙸𝙾𝙳 - 1$ .

Example

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

The $𝚙𝚎𝚛𝚒𝚘𝚍_𝚎𝚡𝚌𝚎𝚙𝚝_0$ constraint holds since, as depicted by Figure 5.320.1, its first argument $𝙿𝙴𝚁𝙸𝙾𝙳 = 3$ is equal (i.e., since $𝙲𝚃𝚁$ is set to $=$ ) to the period of the sequence $11411011$ ; value 0 is assumed to be equal to any other value.

Figure 5.320.1. A sequence that has a period of 3 when we assume that value 0 can match to any other value

Typical

𝙿𝙴𝚁𝙸𝙾𝙳 > 1

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

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

𝚛𝚊𝚗𝚐𝚎

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

𝚊𝚝𝚕𝚎𝚊𝚜𝚝

(1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 0)

𝙲𝚃𝚁 \in [=]

Symmetries

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

Arg. properties

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

Usage

Useful for timetabling problems where a person should repeat some work pattern over an over except when he is unavailable for some reason. The value 0 represents the fact that he is unavailable, while the other values are used in the work pattern.

Algorithm

See [BeldiceanuPoder04].

See also

hard version: $𝚙𝚎𝚛𝚒𝚘𝚍$ .

implied by: $𝚙𝚎𝚛𝚒𝚘𝚍$ .

Keywords

characteristic of a constraint: joker value.

combinatorial object: periodic, sequence.

constraint arguments: pure functional dependency.

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

modelling: functional dependency.

Global Constraint Catalog

5. Global Constraint Catalogue

5.320. period_except_0

Figure 5.320.1. A sequence that has a period of 3 when we assume that value 0 can match to any other value