5.191. lex_alldifferent

DESCRIPTIONLINKSGRAPH
Origin

J.Β Pearson

Constraint

πš•πšŽπš‘_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(πš…π™΄π™²πšƒπ™Ύπšπš‚)

Synonyms

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

Type
πš…π™΄π™²πšƒπ™ΎπšπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Argument
πš…π™΄π™²πšƒπ™Ύπšπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚟𝚎𝚌-πš…π™΄π™²πšƒπ™Ύπš)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπš,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπšπš‚,𝚟𝚎𝚌)
πšœπšŠπš–πšŽ_πšœπš’πš£πšŽ(πš…π™΄π™²πšƒπ™Ύπšπš‚,𝚟𝚎𝚌)
Purpose

All the vectors of the collection πš…π™΄π™²πšƒπ™Ύπšπš‚ are distinct. Two vectors (u 1 ,u 2 ,...,u n ) and (v 1 ,v 2 ,...,v n ) are distinct if and only if there exists i∈[1,n] such that u i β‰ v i .

Example
𝚟𝚎𝚌-5,2,3,𝚟𝚎𝚌-5,2,6,𝚟𝚎𝚌-5,3,3

The πš•πšŽπš‘_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint holds since:

  • The first vector 〈5,2,3βŒͺ and the second vector 〈5,2,6βŒͺ of the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection differ in their third component (i.e.,Β 3β‰ 6).

  • The first vector 〈5,2,3βŒͺ and the third vector 〈5,3,3βŒͺ of the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection differ in their second component (i.e.,Β 2β‰ 3).

  • The second vector 〈5,2,6βŒͺ and the third vector 〈5,3,3βŒͺ of the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection differ in their second and third components (i.e.,Β 2β‰ 3 and 6β‰ 3).

Symmetries
  • Items of πš…π™΄π™²πšƒπ™Ύπšπš‚ are permutable.

  • Items of πš…π™΄π™²πšƒπ™Ύπšπš‚.𝚟𝚎𝚌 are permutable (same permutation used).

  • All occurrences of two distinct tuples of values of πš…π™΄π™²πšƒπ™Ύπšπš‚.𝚟𝚎𝚌 can be swapped; all occurrences of a tuple of values of πš…π™΄π™²πšƒπ™Ύπšπš‚.𝚟𝚎𝚌 can be renamed to any unused tuple of values.

Usage

When the vectors have two components, the πš•πšŽπš‘_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint allows to directly enforce difference constraints between pairs of variables. Such difference constraints occur for instance in block design problems (e.g.,Β Steiner triples, Kirkman schoolgirls problem). However, in all these problems a same variable may occur in more than one pair of variables. Consequently, arc-consistency is not achieved any more by the filtering algorithm described inΒ [QuimperWalsh05].

Algorithm

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

Reformulation

The πš•πšŽπš‘_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(πš…π™΄π™²πšƒπ™Ύπšπš‚) constraint can be expressed as a clique of πš•πšŽπš‘_πšπš’πšπšπšŽπš›πšŽπš—πš constraints. By associating a n -dimensional box for which all sizes are equal to 1, one can also express the πš•πšŽπš‘_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(πš…π™΄π™²πšƒπ™Ύπšπš‚) constraint as a πšπš’πšπšπš— or a 𝚐𝚎𝚘𝚜𝚝 constraint. Enforcing all the n -dimensional boxes to not overlap is equivalent as enforcing all the vectors to be distinct. In the context of the multidimensional sweep algorithm of the 𝚐𝚎𝚘𝚜𝚝 constraintΒ [BeldiceanuCarlssonPoderSadekTruchet07], it makes more sense to make a complete sweep over the domain of each variable in order not to only restrict the minimum and maximum value of each variable.

See also

generalisation: πšπš’πšπšπš—Β (πšŸπšŽπšŒπšπš˜πš› replaced by πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽ), 𝚐𝚎𝚘𝚜𝚝 (πšŸπšŽπšŒπšπš˜πš› replaced by πš˜πš‹πš“πšŽπšŒπš).

implied by: πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœ.

part of system of constraints: πš•πšŽπš‘_πšπš’πšπšπšŽπš›πšŽπš—πš.

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

used in graph description: πš•πšŽπš‘_πšπš’πšπšπšŽπš›πšŽπš—πš.

Keywords

characteristic of a constraint: vector.

constraint type: system of constraints, decomposition.

filtering: bipartite matching, arc-consistency.

modelling: difference between pairs of variables.

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.191.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.191.1. Initial and final graph of the πš•πšŽπš‘_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint
ctrs/lex_alldifferentActrs/lex_alldifferentB
(a) (b)
Signature

Since we use the πΆπΏπΌπ‘„π‘ˆπΈ(<) arc generator on the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection the number of arcs of the initial graph is equal to |πš…π™΄π™²πšƒπ™Ύπšπš‚|Β·(|πš…π™΄π™²πšƒπ™Ύπšπš‚|-1)/2. For this reason we can rewrite 𝐍𝐀𝐑𝐂=|πš…π™΄π™²πšƒπ™Ύπšπš‚|Β·(|πš…π™΄π™²πšƒπ™Ύπšπš‚|-1)/2 to 𝐍𝐀𝐑𝐂β‰₯|πš…π™΄π™²πšƒπ™Ύπšπš‚|Β·(|πš…π™΄π™²πšƒπ™Ύπšπš‚|-1)/2 and simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.