5.269. period_except_0

DESCRIPTIONLINKS
Origin

Derived from πš™πšŽπš›πš’πš˜πš.

Constraint

πš™πšŽπš›πš’πš˜πš_πšŽπš‘πšŒπšŽπš™πš_0(π™Ώπ™΄πšπ™Έπ™Ύπ™³,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,π™²πšƒπš)

Arguments
π™Ώπ™΄πšπ™Έπ™Ύπ™³πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
π™²πšƒπšπšŠπšπš˜πš–
Restrictions
π™Ώπ™΄πšπ™Έπ™Ύπ™³β‰₯1
π™Ώπ™΄πšπ™Έπ™Ύπ™³β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
π™²πšƒπšβˆˆ[=,β‰ ,<,β‰₯,>,≀]
Purpose

Let us note V 0 ,V 1 ,...,V m-1 the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. π™Ώπ™΄πšπ™Έπ™Ύπ™³ is the period of the sequence V 0 V 1 ...V m-1 according to constraint π™²πšƒπš . This means that π™Ώπ™΄πšπ™Έπ™Ύπ™³ is the smallest natural number such that V i π™²πšƒπš V i+π™Ώπ™΄πšπ™Έπ™Ύπ™³ ∨V i =0∨V i+π™Ώπ™΄πšπ™Έπ™Ύπ™³ =0 holds for all i∈0,1,...,m-π™Ώπ™΄πšπ™Έπ™Ύπ™³-1.

Example
3,πšŸπšŠπš›-1,πšŸπšŠπš›-1,πšŸπšŠπš›-4,πšŸπšŠπš›-1,πšŸπšŠπš›-1,πšŸπšŠπš›-0,πšŸπšŠπš›-1,πšŸπšŠπš›-1,=

The πš™πšŽπš›πš’πš˜πš_πšŽπš‘πšŒπšŽπš™πš_0 constraint holds since, as depicted by FigureΒ 5.269.1, its first argument π™Ώπ™΄πšπ™Έπ™Ύπ™³=3 is equal (i.e.,Β since π™²πšƒπš is set to =) to the period of the sequence 1 1 4 1 1 0 1 1; value 0 is assumed to be equal to any other value.

Figure 5.269.1. A sequence that has a period of 3 when we assume that value 0 can be equal to any other value
ctrs/period_except_01
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.

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 type: predefined constraint, timetabling constraint, scheduling constraint.