## 5.13. alldifferent_between_sets

Origin

ILOG

Constraint

Synonyms

$\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }$, , , $\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi }_\mathrm{\pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi }_\mathrm{\pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi }_\mathrm{\pi \pi \pi \pi }$.

Argument
 $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$
Restriction
$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)$
Purpose

Enforce all sets of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ to be distinct.

Example
$\left(β©\mathrm{\pi \pi \pi }-\left\{3,5\right\},\mathrm{\pi \pi \pi }-\mathrm{\beta  },\mathrm{\pi \pi \pi }-\left\{3\right\},\mathrm{\pi \pi \pi }-\left\{3,5,7\right\}βͺ\right)$

The constraint holds since all the sets $\left\{3,5\right\}$, $\mathrm{\beta  }$, $\left\{3\right\}$ and $\left\{3,5,7\right\}$ are distinct.

Typical
$|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>2$
Symmetry

Items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ are permutable.

Arg. properties

Contractible wrt. $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

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].

specialisation: $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi }\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$).

Keywords
Arc input(s)

$\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$

Arc generator
$\mathrm{\pi Ά\pi Ώ\pi Ό\pi \pi \pi Έ}$$\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1},\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{\pi \pi }_\mathrm{\pi \pi \pi }$$\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi }\right)$
Graph property(ies)
$\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$$\beta €1$

Graph class
$\mathrm{\pi Ύ\pi ½\pi ΄}_\mathrm{\pi \pi \pi ²\pi ²}$

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.13.1 respectively show the initial and final graph associated with the Example slot. Since we use the $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ graph property we show one of the largest strongly connected components of the final graph. The holds since all the strongly connected components have at most one vertex.