5.51. change_pair

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from πšŒπš‘πšŠπš—πšπšŽ.

Constraint

πšŒπš‘πšŠπš—πšπšŽ_πš™πšŠπš’πš›(𝙽𝙲𝙷𝙰𝙽𝙢𝙴,π™Ώπ™°π™Έπšπš‚,π™²πšƒπšπš‡,π™²πšƒπšπšˆ)

Arguments
π™½π™²π™·π™°π™½π™Άπ™΄πšπšŸπšŠπš›
π™Ώπ™°π™Έπšπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚑-πšπšŸπšŠπš›,𝚒-πšπšŸπšŠπš›)
π™²πšƒπšπš‡πšŠπšπš˜πš–
π™²πšƒπšπšˆπšŠπšπš˜πš–
Restrictions
𝙽𝙲𝙷𝙰𝙽𝙢𝙴β‰₯0
𝙽𝙲𝙷𝙰𝙽𝙢𝙴<|π™Ώπ™°π™Έπšπš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(π™Ώπ™°π™Έπšπš‚,[𝚑,𝚒])
π™²πšƒπšπš‡βˆˆ[=,β‰ ,<,β‰₯,>,≀]
π™²πšƒπšπšˆβˆˆ[=,β‰ ,<,β‰₯,>,≀]
Purpose

𝙽𝙲𝙷𝙰𝙽𝙢𝙴 is the number of times that the following disjunction holds: (X 1 π™²πšƒπšπš‡ X 2 )∨(Y 1 π™²πšƒπšπšˆ Y 2 ), where (X 1 ,Y 1 ) and (X 2 ,Y 2 ) correspond to consecutive pairs of variables of the collection π™Ώπ™°π™Έπšπš‚.

Example
3,𝚑-3𝚒-5,𝚑-3𝚒-7,𝚑-3𝚒-7,𝚑-3𝚒-8,𝚑-3𝚒-4,𝚑-3𝚒-7,𝚑-1𝚒-3,𝚑-1𝚒-6,𝚑-1𝚒-6,𝚑-3𝚒-7,β‰ ,>

In the example we have the following 3 changes:

  • One change between pairs 𝚑-3 𝚒-8 and 𝚑-3 𝚒-4 since 3β‰ 3∨8>4,

  • One change between pairs 𝚑-3 𝚒-7 and 𝚑-1 𝚒-3 since 3β‰ 1∨7>3,

  • One change between pairs 𝚑-1 𝚒-6 and 𝚑-3 𝚒-7 since 1β‰ 3∨6>7.

Consequently the πšŒπš‘πšŠπš—πšπšŽ_πš™πšŠπš’πš› constraint holds since its first argument 𝙽𝙲𝙷𝙰𝙽𝙢𝙴 is assigned to 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 π™Ώπ™°π™Έπšπš‚.

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

specialisation: πšŒπš‘πšŠπš—πšπšŽΒ (πš™πšŠπš’πš› of πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ).

Keywords

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

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

constraint type: timetabling constraint.

final graph structure: acyclic, bipartite, no loop.

modelling: number of changes.

Arc input(s)

π™Ώπ™°π™Έπšπš‚

Arc generator
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš™πšŠπš’πš›πšœ1,πš™πšŠπš’πš›πšœ2)

Arc arity
Arc constraint(s)
πš™πšŠπš’πš›πšœ1.𝚑 π™²πšƒπšπš‡ πš™πšŠπš’πš›πšœ2.πš‘βˆ¨πš™πšŠπš’πš›πšœ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.51.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.51.1. Initial and final graph of the πšŒπš‘πšŠπš—πšπšŽ_πš™πšŠπš’πš› constraint
ctrs/change_pairActrs/change_pairB
(a) (b)
Automaton

FigureΒ 5.51.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 πš‚ i . The following signature constraint links πš‡ i , 𝚈 i , πš‡ i+1 , 𝚈 i+1 and πš‚ i : (πš‡ i π™²πšƒπšπš‡ πš‡ i+1 )∨(𝚈 i π™²πšƒπšπšˆ 𝚈 i+1 )β‡”πš‚ i .

Figure 5.51.2. Automaton of the πšŒπš‘πšŠπš—πšπšŽ_πš™πšŠπš’πš› constraint
ctrs/change_pair1
Figure 5.51.3. Hypergraph of the reformulation corresponding to the automaton of the πšŒπš‘πšŠπš—πšπšŽ_πš™πšŠπš’πš› constraint
ctrs/change_pair2