Global Constraint Catalog: Cchange

5.63. change_pair

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Derived from $𝚌𝚑𝚊𝚗𝚐𝚎$ .

Constraint

$𝚌𝚑𝚊𝚗𝚐𝚎_𝚙𝚊𝚒𝚛 (𝙽𝙲𝙷𝙰𝙽𝙶𝙴, 𝙿𝙰𝙸𝚁𝚂, 𝙲𝚃𝚁𝚇, 𝙲𝚃𝚁𝚈)$

Arguments

$𝙽𝙲𝙷𝙰𝙽𝙶𝙴$	$𝚍𝚟𝚊𝚛$
$𝙿𝙰𝙸𝚁𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚡 - 𝚍𝚟𝚊𝚛, 𝚢 - 𝚍𝚟𝚊𝚛)$
$𝙲𝚃𝚁𝚇$	$𝚊𝚝𝚘𝚖$
$𝙲𝚃𝚁𝚈$	$𝚊𝚝𝚘𝚖$

Restrictions

𝙽𝙲𝙷𝙰𝙽𝙶𝙴 \geq 0

𝙽𝙲𝙷𝙰𝙽𝙶𝙴 < | 𝙿𝙰𝙸𝚁𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙿𝙰𝙸𝚁𝚂, [𝚡, 𝚢])

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

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

Purpose

$𝙽𝙲𝙷𝙰𝙽𝙶𝙴$ is the number of times that the following disjunction holds: $(X_{1} 𝙲𝚃𝚁𝚇 X_{2}) \lor (Y_{1} 𝙲𝚃𝚁𝚈 Y_{2})$ , where $(X_{1}, Y_{1})$ and $(X_{2}, Y_{2})$ correspond to consecutive pairs of variables of the collection $𝙿𝙰𝙸𝚁𝚂$ .

Example

(\begin{matrix} 3, 〈\begin{matrix} 𝚡 - 3 & 𝚢 - 5, \\ 𝚡 - 3 & 𝚢 - 7, \\ 𝚡 - 3 & 𝚢 - 7, \\ 𝚡 - 3 & 𝚢 - 8, \\ 𝚡 - 3 & 𝚢 - 4, \\ 𝚡 - 3 & 𝚢 - 7, \\ 𝚡 - 1 & 𝚢 - 3, \\ 𝚡 - 1 & 𝚢 - 6, \\ 𝚡 - 1 & 𝚢 - 6, \\ 𝚡 - 3 & 𝚢 - 7 \end{matrix}〉, \neq, > \end{matrix})

In the example we have the following 3 changes:

One change between pairs $𝚡 - 3$ $𝚢 - 8$ and $𝚡 - 3$ $𝚢 - 4$ since $3 \neq 3 \lor 8 > 4$ ,
One change between pairs $𝚡 - 3$ $𝚢 - 7$ and $𝚡 - 1$ $𝚢 - 3$ since $3 \neq 1 \lor 7 > 3$ ,
One change between pairs $𝚡 - 1$ $𝚢 - 6$ and $𝚡 - 3$ $𝚢 - 7$ since $1 \neq 3 \lor 6 > 7$ .

Consequently the $𝚌𝚑𝚊𝚗𝚐𝚎_𝚙𝚊𝚒𝚛$ constraint holds since its first argument $𝙽𝙲𝙷𝙰𝙽𝙶𝙴$ is assigned value 3.

Typical

𝙽𝙲𝙷𝙰𝙽𝙶𝙴 > 0

| 𝙿𝙰𝙸𝚁𝚂 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝙿𝙰𝙸𝚁𝚂 . 𝚡) > 1

𝚛𝚊𝚗𝚐𝚎

(𝙿𝙰𝙸𝚁𝚂 . 𝚢) > 1

Symmetries

One and the same constant can be added to the $𝚡$ attribute of all items of $𝙿𝙰𝙸𝚁𝚂$ .
One and the same constant can be added to the $𝚢$ attribute of all items of $𝙿𝙰𝙸𝚁𝚂$ .

Arg. properties

Functional dependency: $𝙽𝙲𝙷𝙰𝙽𝙶𝙴$ determined by $𝙿𝙰𝙸𝚁𝚂$ , $𝙲𝚃𝚁𝚇$ and $𝙲𝚃𝚁𝚈$ .

Usage

Here is a typical example where this constraint is useful. Assume we have to produce a set of cables. A given quality and a given cross-section that respectively correspond to the $𝚡$ and $𝚢$ attributes of the previous pairs of variables characterise each cable. The problem is to sequence the different cables in order to minimise the number of times two consecutive wire cables $C_{1}$ and $C_{2}$ verify the following property: $C_{1}$ and $C_{2}$ do not have the same quality or the cross section of $C_{1}$ is greater than the cross section of $C_{2}$ .

See also

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

specialisation: $𝚌𝚑𝚊𝚗𝚐𝚎$ ( $𝚙𝚊𝚒𝚛$ of $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ ).

Keywords

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

constraint arguments: pure functional dependency.

constraint network structure: sliding cyclic(2) 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 . 𝚡 𝙲𝚃𝚁𝚇 𝚙𝚊𝚒𝚛𝚜 2 . 𝚡 \lor 𝚙𝚊𝚒𝚛𝚜 1 . 𝚢 𝙲𝚃𝚁𝚈 𝚙𝚊𝚒𝚛𝚜 2 . 𝚢

Graph property(ies)

𝐍𝐀𝐑𝐂

= 𝙽𝙲𝙷𝙰𝙽𝙶𝙴

Graph class

•

𝙰𝙲𝚈𝙲𝙻𝙸𝙲

•

𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴

•

𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

Same as $𝚌𝚑𝚊𝚗𝚐𝚎$ , except that each item has two attributes $𝚡$ and $𝚢$ .

Parts (A) and (B) of Figure 5.63.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.63.1. Initial and final graph of the $𝚌𝚑𝚊𝚗𝚐𝚎_𝚙𝚊𝚒𝚛$ constraint


(a)	(b)

Automaton: Figure 5.63.2 depicts the automaton associated with the $𝚌𝚑𝚊𝚗𝚐𝚎_𝚙𝚊𝚒𝚛$ constraint. To each pair of consecutive pairs $((𝚇_{i}, 𝚈_{i}), (𝚇_{i + 1}, 𝚈_{i + 1}))$ of the collection $𝙿𝙰𝙸𝚁𝚂$ corresponds a 0-1 signature variable $S_{i}$ . The following signature constraint links $𝚇_{i}$ , $𝚈_{i}$ , $𝚇_{i + 1}$ , $𝚈_{i + 1}$ and $S_{i}$ : $(𝚇_{i} 𝙲𝚃𝚁𝚇 𝚇_{i + 1}) \lor (𝚈_{i} 𝙲𝚃𝚁𝚈 𝚈_{i + 1}) \Leftrightarrow S_{i}$ .

Figure 5.63.2. Automaton of the $𝚌𝚑𝚊𝚗𝚐𝚎_𝚙𝚊𝚒𝚛$ constraint

Figure 5.63.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚌𝚑𝚊𝚗𝚐𝚎_𝚙𝚊𝚒𝚛$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.63. change_pair

Figure 5.63.1. Initial and final graph of the $𝚌𝚑𝚊𝚗𝚐𝚎_𝚙𝚊𝚒𝚛$ constraint

Figure 5.63.2. Automaton of the $𝚌𝚑𝚊𝚗𝚐𝚎_𝚙𝚊𝚒𝚛$ constraint

Figure 5.63.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚌𝚑𝚊𝚗𝚐𝚎_𝚙𝚊𝚒𝚛$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.63. change_pair

Figure 5.63.1. Initial and final graph of the 𝚌𝚑𝚊𝚗𝚐𝚎_𝚙𝚊𝚒𝚛 constraint

Figure 5.63.2. Automaton of the 𝚌𝚑𝚊𝚗𝚐𝚎_𝚙𝚊𝚒𝚛 constraint

Figure 5.63.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚌𝚑𝚊𝚗𝚐𝚎_𝚙𝚊𝚒𝚛 constraint

Figure 5.63.1. Initial and final graph of the $𝚌𝚑𝚊𝚗𝚐𝚎_𝚙𝚊𝚒𝚛$ constraint

Figure 5.63.2. Automaton of the $𝚌𝚑𝚊𝚗𝚐𝚎_𝚙𝚊𝚒𝚛$ constraint

Figure 5.63.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚌𝚑𝚊𝚗𝚐𝚎_𝚙𝚊𝚒𝚛$ constraint