Global Constraint Catalog: Cchange

5.61. change

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

CHIP

Constraint

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

Synonyms

$𝚗𝚋𝚌𝚑𝚊𝚗𝚐𝚎𝚜$ , $𝚜𝚒𝚖𝚒𝚕𝚊𝚛𝚒𝚝𝚢$ .

Arguments

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

Restrictions

𝙽𝙲𝙷𝙰𝙽𝙶𝙴 \geq 0

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

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

Purpose

$𝙽𝙲𝙷𝙰𝙽𝙶𝙴$ is the number of times that constraint $𝙲𝚃𝚁$ holds on consecutive variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Example

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

(1, 〈1, 2, 4, 3, 7〉, >)

In the first example the changes are located between values 4 and 3, 3 and 4, 4 and 1. Consequently, the corresponding $𝚌𝚑𝚊𝚗𝚐𝚎$ constraint holds since its first argument $𝙽𝙲𝙷𝙰𝙽𝙶𝙴$ is fixed to value 3.

In the second example the unique change occurs between values 4 and 3. Consequently, the corresponding $𝚌𝚑𝚊𝚗𝚐𝚎$ constraint holds since its first argument $𝙽𝙲𝙷𝙰𝙽𝙶𝙴$ is fixed to 1.

All solutions

Figure 5.61.1 gives all solutions to the following non ground instance of the $𝚌𝚑𝚊𝚗𝚐𝚎$ constraint: $𝙽𝙲𝙷𝙰𝙽𝙶𝙴 \in [0, 1]$ , $V_{1} \in [2, 3]$ , $V_{2} \in [1, 2]$ , $V_{3} \in [4, 5]$ , $V_{4} \in [2, 4]$ , $𝚌𝚑𝚊𝚗𝚐𝚎$ $(𝙽𝙲𝙷𝙰𝙽𝙶𝙴, 〈 V_{1}, V_{2}, V_{3}, V_{4} 〉, >)$ .

Figure 5.61.1. All solutions corresponding to the non ground example of the $𝚌𝚑𝚊𝚗𝚐𝚎$ constraint (with $𝙲𝚃𝚁$ set to $>$ ) of the All solutions slot; each change is shown by a color change between two consecutive values.

Typical

𝙽𝙲𝙷𝙰𝙽𝙶𝙴 > 0

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

𝚛𝚊𝚗𝚐𝚎

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

𝙲𝚃𝚁 \in [\neq]

Symmetry

One and the same constant can be added to the $𝚟𝚊𝚛$ attribute of all items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Arg. properties

Functional dependency: $𝙽𝙲𝙷𝙰𝙽𝙶𝙴$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ and $𝙲𝚃𝚁$ .
Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙲𝚃𝚁 \in [\neq, <, \geq, >, \leq]$ and $𝙽𝙲𝙷𝙰𝙽𝙶𝙴 = 0$ .
Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙲𝚃𝚁 \in [=, <, \geq, >, \leq]$ and $𝙽𝙲𝙷𝙰𝙽𝙶𝙴 = | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | - 1$ .

Usage

This constraint can be used in the context of timetabling problems in order to put an upper limit on the number of changes of job types during a given period.

Remark

A similar constraint appears in [PachetRoy99] under the name of $𝚜𝚒𝚖𝚒𝚕𝚊𝚛𝚒𝚝𝚢$ constraint. The difference consists of replacing the arithmetic constraint $𝙲𝚃𝚁$ by a binary constraint. When $𝙲𝚃𝚁$ is equal to $\neq$ this constraint is called $𝚗𝚋𝚌𝚑𝚊𝚗𝚐𝚎𝚜$ in [Platon03].

Algorithm

A first incomplete algorithm is described in [BeldiceanuCarlsson01]. The sketch of a filtering algorithm for the conjunction of the $𝚌𝚑𝚊𝚗𝚐𝚎$ and the $𝚜𝚝𝚛𝚎𝚝𝚌𝚑$ constraints based on dynamic programming achieving arc-consistency is mentioned by L. Hellsten in [Hellsten04].

Reformulation

The $𝚌𝚑𝚊𝚗𝚐𝚎$ constraint can be reformulated with the $𝚜𝚎𝚚_𝚋𝚒𝚗$ constraint [PetitBeldiceanuLorca11] that we now introduce. Given $𝙽$ a domain variable, $𝚇$ a sequence of domain variables, and $𝙲$ and $𝙱$ two binary constraints, $𝚜𝚎𝚚_𝚋𝚒𝚗$ $(𝙽, 𝚇, 𝙲, 𝙱)$ holds if (1) $𝙽$ is equal to the number of $𝙲$ -stretches in the sequence $𝚇$ , and (2) $𝙱$ holds on any pair of consecutive variables in $𝚇$ . A $𝙲$ -stretch is a generalisation of the notion of stretch introduced by G. Pesant [Pesant01], where the equality constraint is made explicit by replacing it by a binary constraint $𝙲$ , i.e., a $𝙲$ -stretch is a maximal length subsequence of $𝚇$ for which the binary constraint $𝙲$ is satisfied on consecutive variables. $𝚌𝚑𝚊𝚗𝚐𝚎$ $(𝙽𝙲𝙷𝙰𝙽𝙶𝙴, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝙲𝚃𝚁)$ can be reformulated as $𝙽 = 𝙽 1 - 1 \land$ $𝚜𝚎𝚚_𝚋𝚒𝚗$ $(𝙽 1, 𝚇, \neg 𝙲𝚃𝚁, true)$ , where $true$ is the universal constraint.

Used in

$𝚙𝚊𝚝𝚝𝚎𝚛𝚗$ .

See also

common keyword: $𝚌𝚑𝚊𝚗𝚐𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ , $𝚌𝚒𝚛𝚌𝚞𝚕𝚊𝚛_𝚌𝚑𝚊𝚗𝚐𝚎$ (number of changes in a sequence of $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜$ with respect to a $𝚋𝚒𝚗𝚊𝚛𝚢 𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝$ ), $𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎$ , $𝚌𝚢𝚌𝚕𝚒𝚌_𝚌𝚑𝚊𝚗𝚐𝚎_𝚓𝚘𝚔𝚎𝚛$ (number of changes), $𝚜𝚖𝚘𝚘𝚝𝚑$ (number of changes in a sequence of $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜$ with respect to a $𝚋𝚒𝚗𝚊𝚛𝚢 𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝$ ).

generalisation: $𝚌𝚑𝚊𝚗𝚐𝚎_𝚙𝚊𝚒𝚛$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ replaced by $𝚙𝚊𝚒𝚛$ of $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜$ ), $𝚌𝚑𝚊𝚗𝚐𝚎_𝚟𝚎𝚌𝚝𝚘𝚛𝚜$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ replaced by vector).

shift of concept: $𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎_𝚌𝚑𝚊𝚗𝚐𝚎$ , $𝚕𝚘𝚗𝚐𝚎𝚜𝚝_𝚌𝚑𝚊𝚗𝚐𝚎$ .

Keywords

characteristic of a constraint: automaton, automaton with counters, non-deterministic automaton.

constraint arguments: pure functional dependency.

constraint network structure: sliding cyclic(1) constraint network(2), Berge-acyclic constraint network.

constraint type: timetabling constraint.

filtering: dynamic programming.

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 . 𝚟𝚊𝚛 𝙲𝚃𝚁 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛

Graph property(ies)

𝐍𝐀𝐑𝐂

= 𝙽𝙲𝙷𝙰𝙽𝙶𝙴

Graph class

•

𝙰𝙲𝚈𝙲𝙻𝙸𝙲

•

𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴

•

𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

Since we are only interested by the constraints linking two consecutive items of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ we use $𝑃𝐴𝑇𝐻$ to generate the arcs of the initial graph.

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

Figure 5.61.2. Initial and final graph of the $𝚌𝚑𝚊𝚗𝚐𝚎$ constraint


(a)	(b)

Automaton

Figure 5.61.3 depicts a first automaton that only accepts all the solutions to the $𝚌𝚑𝚊𝚗𝚐𝚎$ constraint. This automaton uses a counter in order to record the number of satisfied constraints of the form ${𝚅𝙰𝚁}_{i} 𝙲𝚃𝚁 {𝚅𝙰𝚁}_{i + 1}$ already encountered. 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} 𝙲𝚃𝚁 {𝚅𝙰𝚁}_{i + 1} \Leftrightarrow S_{i}$ .

Figure 5.61.3. Automaton (with counter) of the $𝚌𝚑𝚊𝚗𝚐𝚎$ constraint

Figure 5.61.4. Hypergraph of the reformulation corresponding to the automaton (with counter) of the $𝚌𝚑𝚊𝚗𝚐𝚎$ constraint

Since the reformulation associated with the previous automaton is not Berge-acyclic, we now describe a second counter free automaton that also only accepts all the solutions to the $𝚌𝚑𝚊𝚗𝚐𝚎$ constraint. Without loss of generality, assume that the collection of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ contains at least two variables (i.e., $| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | \geq 2$ ). Let $n$ and $𝒟$ respectively denote the number of variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ , and the union of the domains of the variables of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ . Clearly, the maximum number of changes (i.e., the number of times the constraint ${𝚅𝙰𝚁}_{i} 𝙲𝚃𝚁 {𝚅𝙰𝚁}_{i + 1}$ $(1 \leq i < n)$ holds) cannot exceed the quantity $m = min (n - 1, \bar{𝙽𝙲𝙷𝙰𝙽𝙶𝙴})$ . The $(m + 1) \cdot | 𝒟 | + 2$ states of the automaton that only accepts all the solutions to the $𝚌𝚑𝚊𝚗𝚐𝚎$ constraint are defined in the following way:

We have an initial state labelled by $s_{I}$ .
We have $m \cdot | 𝒟 |$ intermediate states labelled by $s_{i j}$ $(i \in 𝒟, j \in [0, m])$ . The first subscript $i$ of state $s_{i j}$ corresponds to the value currently encountered. The second subscript $j$ denotes the number of already encountered satisfied constraints of the form ${𝚅𝙰𝚁}_{i} 𝙲𝚃𝚁 {𝚅𝙰𝚁}_{i + 1}$ from the initial state $s_{I}$ to the state $s_{i j}$ .
We have an accepting state labelled by $s_{F}$ .

Four classes of transitions are respectively defined in the following way:

There is a transition, labelled by $i$ from the initial state $s_{I}$ to the state $s_{i 0}$ , $(i \in 𝒟)$ .
There is a transition, labelled by $j$ , from every state $s_{i j}$ , $(i \in 𝒟, j \in [0, m])$ , to the accepting state $s_{F}$ .
$\forall i \in 𝒟, \forall j \in [0, m], \forall k \in 𝒟 \cap {k | i \neg 𝙲𝚃𝚁 k}$ there is a transition labelled by $k$ from $s_{i j}$ to $s_{k j}$ (i.e., the counter $j$ does not change for values $k$ such that constraint $i 𝙲𝚃𝚁 k$ does not hold).
$\forall i \in 𝒟, \forall j \in [0, m - 1], \forall k \in 𝒟 ∖ {k | i \neg 𝙲𝚃𝚁 k}$ there is a transition labelled by $k$ from $s_{i j}$ to $s_{k j + 1}$ (i.e., the counter $j$ is incremented by $+ 1$ for values $k$ such that constraint $i 𝙲𝚃𝚁 k$ holds).

We have $| 𝒟 |$ transitions of type 1, $| 𝒟 | \cdot (m + 1)$ transitions of type 2, and at least ${| 𝒟 |}^{2} \cdot m$ transitions of types 3 and 4. Since the maximum value of $m$ is equal to $n - 1$ , in the worst case we have at least ${| 𝒟 |}^{2} \cdot (n - 1)$ transitions. This leads to a worst case time complexity of $O (| 𝒟 |^{2} \cdot n^{2})$ if we use Pesant's algorithm for filtering the $𝚛𝚎𝚐𝚞𝚕𝚊𝚛$ constraint [Pesant04].

Figure 5.61.5 depicts the corresponding counter free non deterministic automaton associated with the $𝚌𝚑𝚊𝚗𝚐𝚎$ constraint under the hypothesis that (1) all variables of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are assigned a value in ${0, 1, 2, 3}$ , (2) $| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |$ is equal to 4, and (3) $𝙲𝚃𝚁$ is equal to $\neq$ .

Figure 5.61.5. Counter free non deterministic automaton of the $𝚌𝚑𝚊𝚗𝚐𝚎$ $(𝙽𝙲𝙷𝙰𝙽𝙶𝙴, 〈 {𝚅𝙰𝚁}_{1}, {𝚅𝙰𝚁}_{2}, {𝚅𝙰𝚁}_{3}, {𝚅𝙰𝚁}_{4} 〉, \neq)$ constraint assuming ${𝚅𝙰𝚁}_{i} \in [0, 3]$ $(1 \leq i \leq 3)$ , with initial state $s_{I}$ and accepting state $s_{F}$

Global Constraint Catalog

5. Global Constraint Catalogue

5.61. change

Figure 5.61.1. All solutions corresponding to the non ground example of the 𝚌𝚑𝚊𝚗𝚐𝚎 constraint (with 𝙲𝚃𝚁 set to >) of the All solutions slot; each change is shown by a color change between two consecutive values.

Figure 5.61.2. Initial and final graph of the 𝚌𝚑𝚊𝚗𝚐𝚎 constraint

Figure 5.61.3. Automaton (with counter) of the 𝚌𝚑𝚊𝚗𝚐𝚎 constraint

Figure 5.61.4. Hypergraph of the reformulation corresponding to the automaton (with counter) of the 𝚌𝚑𝚊𝚗𝚐𝚎 constraint

Figure 5.61.5. Counter free non deterministic automaton of the 𝚌𝚑𝚊𝚗𝚐𝚎(𝙽𝙲𝙷𝙰𝙽𝙶𝙴,〈𝚅𝙰𝚁 1 ,𝚅𝙰𝚁 2 ,𝚅𝙰𝚁 3 ,𝚅𝙰𝚁 4 〉,≠) constraint assuming 𝚅𝙰𝚁 i ∈[0,3] (1≤i≤3), with initial state s I and accepting state s F

Figure 5.61.1. All solutions corresponding to the non ground example of the $𝚌𝚑𝚊𝚗𝚐𝚎$ constraint (with $𝙲𝚃𝚁$ set to $>$ ) of the All solutions slot; each change is shown by a color change between two consecutive values.

Figure 5.61.2. Initial and final graph of the $𝚌𝚑𝚊𝚗𝚐𝚎$ constraint

Figure 5.61.3. Automaton (with counter) of the $𝚌𝚑𝚊𝚗𝚐𝚎$ constraint

Figure 5.61.4. Hypergraph of the reformulation corresponding to the automaton (with counter) of the $𝚌𝚑𝚊𝚗𝚐𝚎$ constraint