5.244. open_alldifferent

DESCRIPTIONLINKSGRAPH
Origin

[HoeveRegin06]

Constraint

πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(πš‚,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Synonyms

πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšπš, πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšœπšπš’πš—πšŒπš, πš˜πš™πšŽπš—_πšπš’πšœπšπš’πš—πšŒπš.

Arguments
πš‚πšœπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
πš‚β‰₯1
πš‚β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

Let 𝒱 be the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ for which the corresponding position belongs to the set πš‚. Positions are numbered from 1. Enforce all variables of 𝒱 to take distinct values.

Example
({2,3,4},9,1,9,3)

The πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint holds since the last three (i.e.,Β πš‚={2,3,4}) values of the collection 〈9,1,9,3βŒͺ are distinct.

Symmetry

All occurrences of two distinct values of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› can be swapped; all occurrences of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› can be renamed to any unused value.

Usage

In their articleΒ [HoeveRegin06], W.-J.Β vanΒ Hoeve and J.-C.Β RΓ©gin motivate the πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint by the following scheduling problem. Consider a set of activities (where each activity has a fixed duration 1 and a start variable) that can be processed on two factory lines such that all the activities that will be processed on a given line must be pairwise distinct. This can be modelled by using one πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint for each line, involving all the start variables as well as a set variable whose final value specifies the set of activities assigned to that specific factory line.

Note that this can also be directly modelled by one single πšπš’πšπšπš— constraint. This is done by introducing an assignment variable for each activity. The initial domain of each assignment variable consists of two values that respectively correspond to the two factory lines.

Algorithm

A slight adaptation of the flow model that handles the original πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraintΒ [Regin96] is described inΒ [HoeveRegin06].

See also

common keyword: πšœπš’πš£πšŽ_πš–πšŠπš‘_𝚜𝚎𝚚_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, πšœπš’πš£πšŽ_πš–πšŠπš‘_πšœπšπšŠπš›πšπš’πš—πš_𝚜𝚎𝚚_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (all different,disequality).

generalisation: πš˜πš™πšŽπš—_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’Β (control the number of occurrence of each active valueAn active value corresponds to a value occuring at a position mentionned in the set πš‚. with a counter variable), πš˜πš™πšŽπš—_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™Β (control the number of occurrence of each active value with an interval).

hard version: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

used in graph description: πš’πš—_𝚜𝚎𝚝.

Keywords

characteristic of a constraint: all different, disequality.

constraint arguments: constraint involving set variables.

constraint type: open constraint, soft constraint, value constraint.

filtering: flow.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
β€’ πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
β€’ πš’πš—_𝚜𝚎𝚝(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πš”πšŽπš’,πš‚)
β€’ πš’πš—_𝚜𝚎𝚝(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πš”πšŽπš’,πš‚)
Graph property(ies)
πŒπ€π—_𝐍𝐒𝐂𝐂≀1

Graph class
𝙾𝙽𝙴_πš‚πš„π™²π™²

Graph model

We generate a clique with an equality constraint between each pair of vertices (including a vertex and itself) and state that the size of the largest strongly connected component should not exceed one. Variables for which the corresponding position does not belong to the set πš‚ are removed from the final graph by the second and third conditions of the arc -constraint.

PartsΒ (A) andΒ (B) of FigureΒ 5.244.1 respectively show the initial and final graph associated with the Example slot. Since we use the πŒπ€π—_𝐍𝐒𝐂𝐂 graph property we show one of the largest strongly connected component of the final graph. The πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš holds since all the strongly connected components have at most one vertex: a value is used at most once.

Figure 5.244.1. Initial and final graph of the πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint
ctrs/open_alldifferentActrs/open_alldifferentB
(a) (b)