Global Constraint Catalog: Clex

5.220. lex_alldifferent

DESCRIPTION

LINKS

GRAPH

Origin

J. Pearson

Constraint

$𝚕𝚎𝚡_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝 (𝚅𝙴𝙲𝚃𝙾𝚁𝚂)$

Synonyms

$𝚕𝚎𝚡_𝚊𝚕𝚕𝚍𝚒𝚏𝚏$ , $𝚕𝚎𝚡_𝚊𝚕𝚕𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝$ , $𝚊𝚕𝚕𝚍𝚒𝚏𝚏_𝚘𝚗_𝚝𝚞𝚙𝚕𝚎𝚜$ , $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚘𝚗_𝚝𝚞𝚙𝚕𝚎𝚜$ , $𝚊𝚕𝚕𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝_𝚘𝚗_𝚝𝚞𝚙𝚕𝚎𝚜$ .

Type

𝚅𝙴𝙲𝚃𝙾𝚁

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)

Argument

𝚅𝙴𝙲𝚃𝙾𝚁𝚂

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚎𝚌 - 𝚅𝙴𝙲𝚃𝙾𝚁)

Restrictions

| 𝚅𝙴𝙲𝚃𝙾𝚁 | \geq 1

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙴𝙲𝚃𝙾𝚁, 𝚟𝚊𝚛)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙴𝙲𝚃𝙾𝚁𝚂, 𝚟𝚎𝚌)

𝚜𝚊𝚖𝚎_𝚜𝚒𝚣𝚎

(𝚅𝙴𝙲𝚃𝙾𝚁𝚂, 𝚟𝚎𝚌)

Purpose

All the vectors of the collection $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ are distinct. Two vectors $(u_{1}, u_{2}, \dots, u_{n})$ and $(v_{1}, v_{2}, \dots, v_{n})$ are distinct if and only if there exists $i \in [1, n]$ such that $u_{i} \neq 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 \neq 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 \neq 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 \neq 3$ and $6 \neq 3$ ).

Typical

| 𝚅𝙴𝙲𝚃𝙾𝚁 | > 1

| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | > 1

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.

Arg. properties

Contractible wrt. $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ .
Extensible wrt. $𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌$ (add items at same position).

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: $𝚊𝚕𝚕_𝚒𝚗𝚌𝚘𝚖𝚙𝚊𝚛𝚊𝚋𝚕𝚎$ , $𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚐𝚛𝚎𝚊𝚝𝚎𝚛$ , $𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜$ .

implies: $𝚕𝚎𝚡_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚎𝚡𝚌𝚎𝚙𝚝_0$ .

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

𝐶𝐿𝐼𝑄𝑈𝐸

(<) \mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚎𝚌𝚝𝚘𝚛𝚜 1, 𝚟𝚎𝚌𝚝𝚘𝚛𝚜 2)

Arc arity

Arc constraint(s)

𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝

(𝚟𝚎𝚌𝚝𝚘𝚛𝚜 1 . 𝚟𝚎𝚌, 𝚟𝚎𝚌𝚝𝚘𝚛𝚜 2 . 𝚟𝚎𝚌)

Graph property(ies)

𝐍𝐀𝐑𝐂

= | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | * (| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | - 1) / 2

Graph model

Parts (A) and (B) of Figure 5.220.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.220.1. Initial and final graph of the $𝚕𝚎𝚡_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint


(a)	(b)

Signature

Since we use the $𝐶𝐿𝐼𝑄𝑈𝐸 (<)$ arc generator on the $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ collection the number of arcs of the initial graph is equal to $| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | \cdot (| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | - 1) / 2$ . For this reason we can rewrite $𝐍𝐀𝐑𝐂 = | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | \cdot (| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | - 1) / 2$ to $𝐍𝐀𝐑𝐂 \geq | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | \cdot (| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | - 1) / 2$ and simplify $\underset{̲}{\bar{𝐍𝐀𝐑𝐂}}$ to $\bar{𝐍𝐀𝐑𝐂}$ .

Global Constraint Catalog

5. Global Constraint Catalogue

5.220. lex_alldifferent

Figure 5.220.1. Initial and final graph of the 𝚕𝚎𝚡_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝 constraint

Figure 5.220.1. Initial and final graph of the $𝚕𝚎𝚡_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint