5.177. k_disjoint

DESCRIPTIONLINKSGRAPH
Origin

Derived from πšπš’πšœπš“πš˜πš’πš—πš

Constraint

πš”_πšπš’πšœπš“πš˜πš’πš—πš(πš‚π™΄πšƒπš‚)

Type
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Argument
πš‚π™΄πšƒπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚜𝚎𝚝-πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>0
πš›πšŽπššπšžπš’πš›πšŽπš(πš‚π™΄πšƒπš‚,𝚜𝚎𝚝)
|πš‚π™΄πšƒπš‚|>1
Purpose

Given |πš‚π™΄πšƒπš‚| sets of domain variables, the πš”_πšπš’πšœπš“πš˜πš’πš—πš constraint enforces that no value is assigned to more than one set.

Example
𝚜𝚎𝚝-1,9,1,5,𝚜𝚎𝚝-πšŸπšŠπš›-2,πšŸπšŠπš›-7,πšŸπšŠπš›-7,πšŸπšŠπš›-0,πšŸπšŠπš›-6,πšŸπšŠπš›-8,𝚜𝚎𝚝-4,4,3

The πš”_πšπš’πšœπš“πš˜πš’πš—πš constraint holds since:

  • The set of values {1,5,9} and {0,2,6,7,8} respectively assigned to the variables of the first and second collections have an empty intersection.

  • The set of values {1,5,9} and {3,4} respectively assigned to the variables of the first and third collections have an empty intersection.

  • The set of values {0,2,6,7,8} and {3,4} respectively assigned to the variables of the second and third collections have an empty intersection.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
Symmetries
  • Items of πš‚π™΄πšƒπš‚ are permutable.

  • Items of πš‚π™΄πšƒπš‚.𝚜𝚎𝚝 are permutable.

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› can be replaced by any value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›.

  • All occurrences of two distinct values of πš‚π™΄πšƒπš‚.𝚜𝚎𝚝.πšŸπšŠπš› can be swapped; all occurrences of a value of πš‚π™΄πšƒπš‚.𝚜𝚎𝚝.πšŸπšŠπš› can be renamed to any unused value.

See also

part of system of constraints: πšπš’πšœπš“πš˜πš’πš—πš.

used in graph description: πšπš’πšœπš“πš˜πš’πš—πš.

Keywords

characteristic of a constraint: disequality.

constraint type: system of constraints, decomposition, value constraint.

modelling: empty intersection.

Arc input(s)

πš‚π™΄πšƒπš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈ(<)β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚜𝚎𝚝1,𝚜𝚎𝚝2)

Arc arity
Arc constraint(s)
πšπš’πšœπš“πš˜πš’πš—πš(𝚜𝚎𝚝1.𝚜𝚎𝚝,𝚜𝚎𝚝2.𝚜𝚎𝚝)
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš‚π™΄πšƒπš‚|*(|πš‚π™΄πšƒπš‚|-1)/2

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.177.1 respectively show the initial and final graph associated with the Example slot. To each vertex corresponds a collection of variables, while to each arc corresponds a πšπš’πšœπš“πš˜πš’πš—πš constraint.

Figure 5.177.1. Initial and final graph of the πš”_πšπš’πšœπš“πš˜πš’πš—πš constraint
ctrs/k_disjointActrs/k_disjointB
(a) (b)