5.6. alldifferent_between_sets

DESCRIPTIONLINKSGRAPH
Origin

ILOG

Constraint

πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš‹πšŽπšπš πšŽπšŽπš—_𝚜𝚎𝚝𝚜(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Synonyms

πšŠπš•πš•_πš—πšžπš•πš•_πš’πš—πšπšŽπš›πšœπšŽπšŒπš, πšŠπš•πš•πšπš’πšπš_πš‹πšŽπšπš πšŽπšŽπš—_𝚜𝚎𝚝𝚜, πšŠπš•πš•πšπš’πšœπšπš’πš—πšŒπš_πš‹πšŽπšπš πšŽπšŽπš—_𝚜𝚎𝚝𝚜, πšŠπš•πš•πšπš’πšπš_πš˜πš—_𝚜𝚎𝚝𝚜, πšŠπš•πš•πšπš’πšœπšπš’πš—πšŒπš_πš˜πš—_𝚜𝚎𝚝𝚜, πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš˜πš—_𝚜𝚎𝚝𝚜.

Argument
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšœπšŸπšŠπš›)
Restriction
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

Enforce all sets of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ to be distinct.

Example
πšŸπšŠπš›-{3,5},πšŸπšŠπš›-βˆ…,πšŸπšŠπš›-{3},πšŸπšŠπš›-{3,5,7}

The πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš‹πšŽπšπš πšŽπšŽπš—_𝚜𝚎𝚝𝚜 constraint holds since all the sets {3,5}, βˆ…, {3} and {3,5,7} are distinct.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>2
Symmetry

Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

Usage

This constraint was available in some configuration library offered by Ilog.

Algorithm

A filtering algorithm for the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš‹πšŽπšπš πšŽπšŽπš—_𝚜𝚎𝚝𝚜 is proposed by C.-G.Β Quimper and T.Β Walsh inΒ [QuimperWalsh05] and a longer version is available inΒ [QuimperWalshReport05] and inΒ [QuimperWalsh06].

See also

common keyword: πš•πš’πš—πš”_𝚜𝚎𝚝_𝚝𝚘_πš‹πš˜πš˜πš•πšŽπšŠπš—πšœΒ (constraint involving set variables).

specialisation: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (𝚜𝚎𝚝 πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ).

used in graph description: 𝚎𝚚_𝚜𝚎𝚝.

Keywords

characteristic of a constraint: all different, disequality.

constraint arguments: constraint involving set variables.

filtering: bipartite matching.

final graph structure: one_succ.

Arc input(s)

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

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

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

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

Graph model

We generate a clique with binary set equalities constraints between each pair of vertices (including a vertex and itself) and state that the size of the largest strongly connected component should not exceed 1.

PartsΒ (A) andΒ (B) of FigureΒ 5.6.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.

Figure 5.6.1. Initial and final graph of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš‹πšŽπšπš πšŽπšŽπš—_𝚜𝚎𝚝𝚜 constraint
ctrs/alldifferent_between_setsA
(a)
ctrs/alldifferent_between_setsB
(b)