Global Constraint Catalog: Ccyclic

5.107. cyclic_change

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Derived from $𝚌𝚑𝚊𝚗𝚐𝚎$ .

Constraint

$𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎 (𝙽𝙲𝙷𝙰𝙽𝙶𝙴, 𝙲𝚈𝙲𝙻𝙴_𝙻𝙴𝙽𝙶𝚃𝙷, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝙲𝚃𝚁)$

Arguments

$𝙽𝙲𝙷𝙰𝙽𝙶𝙴$	$𝚍𝚟𝚊𝚛$
$𝙲𝚈𝙲𝙻𝙴_𝙻𝙴𝙽𝙶𝚃𝙷$	$𝚒𝚗𝚝$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝙲𝚃𝚁$	$𝚊𝚝𝚘𝚖$

Restrictions

𝙽𝙲𝙷𝙰𝙽𝙶𝙴 \geq 0

𝙽𝙲𝙷𝙰𝙽𝙶𝙴 < | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝙲𝚈𝙲𝙻𝙴_𝙻𝙴𝙽𝙶𝚃𝙷 > 0

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛 \geq 0

𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛 < 𝙲𝚈𝙲𝙻𝙴_𝙻𝙴𝙽𝙶𝚃𝙷

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

Purpose

$𝙽𝙲𝙷𝙰𝙽𝙶𝙴$ is the number of times that constraint $((X + 1) \mod 𝙲𝚈𝙲𝙻𝙴_𝙻𝙴𝙽𝙶𝚃𝙷) 𝙲𝚃𝚁 Y$ holds; $X$ and $Y$ correspond to consecutive variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Example

(2, 4, 〈3, 0, 2, 3, 1〉, \neq)

Since $𝙲𝚃𝚁$ is set to $\neq$ and since $𝙲𝚈𝙲𝙻𝙴_𝙻𝙴𝙽𝙶𝚃𝙷$ is set to 4, a change between two consecutive items $X$ and $Y$ of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection corresponds to the fact that the condition $((X + 1) \mod 4) \neq Y$ holds. Consequently, the $𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint holds since we have the two following changes (i.e., $𝙽𝙲𝙷𝙰𝙽𝙶𝙴 = 2$ ) within $〈 3, 0, 2, 3, 1 〉$ :

A first change between the consecutive values 0 and 2,
A second change between the consecutive values 3 and 1.

However, the sequence $30$ does not correspond to a change since $(3 + 1) \mod 4$ is equal to 0.

Typical

𝙽𝙲𝙷𝙰𝙽𝙶𝙴 > 0

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

𝚛𝚊𝚗𝚐𝚎

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

𝙲𝚃𝚁 \in [\neq]

Symmetry

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ can be shifted.

Arg. properties

Functional dependency: $𝙽𝙲𝙷𝙰𝙽𝙶𝙴$ determined by $𝙲𝚈𝙲𝙻𝙴_𝙻𝙴𝙽𝙶𝚃𝙷$ , $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ and $𝙲𝚃𝚁$ .

Usage

This constraint may be used for personnel cyclic timetabling problems where each person has to work according to cycles. In this context each variable of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection corresponds to the type of work a person performs on a specific day. Because of some perturbation (e.g., illness, unavailability, variation of the workload) it is in practice not reasonable to ask for perfect cyclic solutions. One alternative is to use the $𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint and to ask for solutions where one tries to minimise the number of cycle breaks (i.e., the variable $𝙽𝙲𝙷𝙰𝙽𝙶𝙴$ ).

implies: $𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎_𝚓𝚘𝚔𝚎𝚛$ .

Keywords

characteristic of a constraint: cyclic, automaton, automaton with counters.

constraint arguments: pure functional dependency.

constraint network structure: sliding cyclic(1) constraint network(2).

constraint type: timetabling constraint.

final graph structure: acyclic, bipartite, no loop.

modelling: number of changes, functional dependency.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝑃𝐴𝑇𝐻

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1, 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2)

Arc arity

Arc constraint(s)

(𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛 + 1) \mod 𝙲𝚈𝙲𝙻𝙴_𝙻𝙴𝙽𝙶𝚃𝙷 𝙲𝚃𝚁 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛

Graph property(ies)

𝐍𝐀𝐑𝐂

= 𝙽𝙲𝙷𝙰𝙽𝙶𝙴

Graph class

•

𝙰𝙲𝚈𝙲𝙻𝙸𝙲

•

𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴

•

𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

Parts (A) and (B) of Figure 5.107.1 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐍𝐀𝐑𝐂$ graph property, the arcs of the final graph are stressed in bold.

Figure 5.107.1. Initial and final graph of the $𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint


(a)	(b)

Automaton: Figure 5.107.2 depicts the automaton associated with the $𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint. To each pair of consecutive variables $({𝚅𝙰𝚁}_{i}, {𝚅𝙰𝚁}_{i + 1})$ of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ corresponds a 0-1 signature variable $S_{i}$ . The following signature constraint links ${𝚅𝙰𝚁}_{i}$ , ${𝚅𝙰𝚁}_{i + 1}$ and $S_{i}$ : $(({𝚅𝙰𝚁}_{i} + 1) \mod 𝙲𝚈𝙲𝙻𝙴_𝙻𝙴𝙽𝙶𝚃𝙷) 𝙲𝚃𝚁 {𝚅𝙰𝚁}_{i + 1} \Leftrightarrow S_{i}$ .

Figure 5.107.2. Automaton of the $𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint

Figure 5.107.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.107. cyclic_change

Figure 5.107.1. Initial and final graph of the $𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint

Figure 5.107.2. Automaton of the $𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint

Figure 5.107.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.107. cyclic_change

Figure 5.107.1. Initial and final graph of the 𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎 constraint

Figure 5.107.2. Automaton of the 𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎 constraint

Figure 5.107.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎 constraint

Figure 5.107.1. Initial and final graph of the $𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint

Figure 5.107.2. Automaton of the $𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint

Figure 5.107.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint