5.52. change_partition

DESCRIPTIONLINKSGRAPH
Origin

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

Constraint

πšŒπš‘πšŠπš—πšπšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—(𝙽𝙲𝙷𝙰𝙽𝙢𝙴,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚)

Type
πš…π™°π™»πš„π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•-πš’πš—πš)
Arguments
π™½π™²π™·π™°π™½π™Άπ™΄πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš™-πš…π™°π™»πš„π™΄πš‚)
Restrictions
|πš…π™°π™»πš„π™΄πš‚|β‰₯1
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
πšπš’πšœπšπš’πš—πšŒπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
𝙽𝙲𝙷𝙰𝙽𝙢𝙴β‰₯0
𝙽𝙲𝙷𝙰𝙽𝙢𝙴<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚,πš™)
|π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚|β‰₯2
Purpose

𝙽𝙲𝙷𝙰𝙽𝙢𝙴 is the number of times that the following constraint holds: X and Y do not belong to the same partition of the collection π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚, where X and Y correspond to consecutive variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Example
2,πšŸπšŠπš›-6,πšŸπšŠπš›-6,πšŸπšŠπš›-2,πšŸπšŠπš›-1,πšŸπšŠπš›-3,πšŸπšŠπš›-3,πšŸπšŠπš›-1,πšŸπšŠπš›-6,πšŸπšŠπš›-2,πšŸπšŠπš›-2,πšŸπšŠπš›-2,πš™-1,3,πš™-4,πš™-2,6

In the example we have the following two changes:

  • One change between values 2 and 1 (since 2 and 1 respectively belong to the third and the first partition),

  • One change between values 1 and 6 (since 1 and 6 respectively belong to the first and the third partition).

Consequently the πšŒπš‘πšŠπš—πšπšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš— constraint holds since its first argument 𝙽𝙲𝙷𝙰𝙽𝙢𝙴 is assigned to 2.

Typical
𝙽𝙲𝙷𝙰𝙽𝙢𝙴>0
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>|π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚|
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ can be reversed.

  • Items of π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚ are permutable.

  • Items of π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚.πš™ are permutable.

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› can be replaced by any other value that also belongs to the same partition of π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚.

Usage

This constraint is useful for the following problem: Assume you have to produce a set of orders, each order belonging to a given family. In the context of the Example slot we have three families that respectively correspond to values 1,3, to value 4 and to values 2,6. We would like to sequence the orders in such a way that we minimise the number of times two consecutive orders do not belong to the same family.

Algorithm

[BeldiceanuCarlsson01].

See also

common keyword: πšŒπš‘πšŠπš—πšπšŽΒ (number of changes in a sequence of πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ with respect to a πš‹πš’πš—πšŠπš›πš’ πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš).

used in graph description: πš’πš—_πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—.

Keywords

characteristic of a constraint: partition.

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.πšŸπšŠπš›,π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚)
Graph property(ies)
𝐍𝐀𝐑𝐂=𝙽𝙲𝙷𝙰𝙽𝙢𝙴

Graph class
β€’ π™°π™²πšˆπ™²π™»π™Έπ™²
β€’ π™±π™Έπ™Ώπ™°πšπšƒπ™Έπšƒπ™΄
β€’ 𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.52.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.52.1. Initial and final graph of the πšŒπš‘πšŠπš—πšπšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš— constraint
ctrs/change_partitionActrs/change_partitionB
(a) (b)