## 5.5. alldifferent

Origin
Constraint

$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$

Synonyms

$\mathrm{\pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\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 variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ to take distinct values.

Example
$\left(β©5,1,9,3βͺ\right)$

The $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint holds since all the values 5, 1, 9 and 3 are distinct.

Typical
$|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>2$
Symmetries
• Items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ are permutable.

• Two distinct values of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }$ can be swapped; a value of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }$ can be renamed to any unused value.

Usage

The $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint occurs in most practical problems directly or indirectly. A classical example is the n-queen chess puzzle problem: Place $n$ queens on a $n$ by $n$ chessboard in such a way that no queen attacks another. Two queens attack each other if they are located on the same column, on the same row or on the same diagonal. This can be modelled as the conjunction of three $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraints. We associate to the ${i}^{th}$ column of the chessboard a domain variable ${X}_{i}$ that gives the row number where the corresponding queen is located. The three $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraints are:

• $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left({X}_{1},{X}_{2}+1,...,{X}_{n}+n-1\right)$ for the upper-left to lower-right diagonals,

• $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left({X}_{1},{X}_{2},...,{X}_{n}\right)$ for the rows,

• $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left({X}_{1}+n-1,{X}_{2}+n-2,...,{X}_{n}\right)$ for the lower right to upper-left diagonals.

They are respectively depicted by partsΒ (A), (C) and (D) of FigureΒ 5.5.1.

A second example taken fromΒ [AsratianDenleyHaggkvist98] when the bipartite graph associated with the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint is convex is a ski assignment problem: βa set of skiers have each specified the smallest and largest skis they will accept from a given set of skisβ. The task is to find a ski for each skier.

Examples such as Costas arrays or Golomb rulers involve one or several $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraints on differences of variables.

Quite often, the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint is also used in conjunction with several $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraints, specially in the context of assignment problemsΒ [pages 372β374][Hooker07book].

Other examples involving several $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraints sharing some variables can be found in the Usage slot of the $\mathrm{\pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint.

Remark

Even if the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint had not this form, it was specified in ALICEΒ [Lauriere76], [Lauriere78] by asking for an injective correspondence between variables and values: . From an algorithmic point of view, the algorithm for computing the cardinality of the maximum matching of a bipartite graph was not used for checking the feasibility of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint, even if the algorithm was already known in 1976. This stands from the fact that the goal of ALICE was to show that a general system could be as efficient as dedicated algorithms. For this reason the concluding part ofΒ [Lauriere76] explicitly mentions the fact that specialized algorithms should be discarded. On the one hand, many people, specially from the OR community, have complained about such radical statementΒ [Roy06]. On the other hand, the motivation of such statement stands from the fact that a truly intelligent system should not rely on black box algorithms, but should rather be able to reconstruct them from some kind of first principle. How to achieve this is still an open question.

Some solvers use in a pre -processing phase before stating all constraints, an algorithm for automatically extracting large cliquesΒ [BronKerbosch73] from a set of binary disequalities in order to replace them by $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraints.

W.-J.Β vanΒ Hoeve provides a survey about the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint inΒ [Hoeve01].

For possible relaxation of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraints see the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi ‘\pi \pi \pi \pi }_\mathtt{0}$, the $\mathrm{\pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ (i.e.,Β $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }$

Within the context of linear programming, relaxations of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint are described inΒ [WilliamsYan01] and inΒ [Hooker07book].

Within the context of constraint-centered search heuristics, G.Β Pesant and A.Β ZanariniΒ [ZanariniPesant07b] have proposed several estimators for evaluating the number of solutions of an $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint (since counting the total number of maximum matchings of the corresponding variable -value graph is #P -completeΒ [Valiant79]). Faster, but less accurate estimators, based on upper bounds of the number of solutions were proposed three years later by the same authorsΒ [ZanariniPesant10].

Given $n$ variables taking their values within the interval $\left[1,n\right]$, the total number of solutions of the corresponding $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint corresponds to the sequence A000142 of the On -Line Encyclopedia of Integer SequencesΒ [Sloane10].

Algorithm

The first complete filtering algorithm was independently found by M.-C.Β CostaΒ [Costa94] and J.-C.Β RΓ©ginΒ [Regin94]. This algorithm is based on a corollary of C.Β Berge that characterises the edges of a graph that belong to a maximum matching but not to allΒ [Berge70].A similar result is in fact given inΒ [Petersen1891]. A short time after, assuming that all variables have no holes in their domain, M.Β Leconte came up with a filtering algorithmΒ [Leconte96] based on edge finding. A first bound-consistency algorithm was proposed by Bleuzen-Guernalec et al.Β [GuernalecColmerauer97]. Later on, two different approaches were used to design bound-consistency algorithms. Both approaches model the constraint as a bipartite graph. The first identifies Hall intervals in this graphΒ [Puget98], [LopezOrtizQuimperTrompBeek03] and the second applies the same algorithm that is used to compute arc-consistency, but achieves a speedup by exploiting the simpler structureΒ [Glover67] of the graphΒ [MehlhornThiel00]. Ian P. Gent et al. discuss inΒ [GentMiguelNightingale08] implementations issues behind the complete filtering algorithm and in particular the computation of the strongly connected components of the residual graph (i.e.,Β a graph constructed from a maximum variable -value matching and from the possible values of the variables of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint), which appears to be the main bottleneck in practice.

From a worst case complexity point of view, assuming that $n$ is the number of variables and $m$ the sum of the domains sizes, we have the following complexity results:

• Complete filtering is achieved in $O\left(m\sqrt{n}\right)$ by RΓ©gin's algorithmΒ [Regin94].

• Range consistency is done in $O\left({n}^{2}\right)$ by Leconte's algorithm [Leconte96].

• Bound-consistency is performed in $O\left(nlogn\right)$ inΒ [Puget98], [MehlhornThiel00], [LopezOrtizQuimperTrompBeek03]. If sort can be achieved in linear time, typically when the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint encodes a permutation,In this context the total number of values that can be assigned to the variables of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint is equal to the number of variables. Under this assumption sorting the variables on their minimum or maximum values can be achieved in linear time. the worst case complexity of the algorithms described inΒ [MehlhornThiel00], [LopezOrtizQuimperTrompBeek03] goes down to $O\left(n\right)$.

Within the context of explanationsΒ [JussienBarichard00], the explanation of the filtering algorithm that achieves arc-consistency for the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint is described inΒ [Rochart05]. Given the residual graph (i.e.,Β a graph constructed from a maximum variable -value matching and from the possible values of the variables of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint), the removal of an arc starting from a vertex belonging to a strongly connected component ${\mathrm{\pi }}_{1}$ to a distinct strongly connected component ${\mathrm{\pi }}_{2}$ is explained by all missing arcs starting from a descendant component of ${\mathrm{\pi }}_{2}$ and ending in an ancestor component of ${\mathrm{\pi }}_{1}$ (i.e.,Β since the addition of any of these missing arcs would merge the strongly connected components ${\mathrm{\pi }}_{1}$ and ${\mathrm{\pi }}_{2}$). Let us illustrate this on a concrete example. For this purpose assume we have the following variables and the values that can potentially be assigned to each of them, $A\beta \left\{1,2\right\}$, $B\beta \left\{1,2\right\}$, $C\beta \left\{2,3,4,6\right\}$, $D\beta \left\{3,4\right\}$, $E\beta \left\{5,6\right\}$, $F\beta \left\{5,6\right\}$, $G\beta \left\{6,7,8\right\}$, $H\beta \left\{6,7,8\right\}$. FigureΒ 5.5.2 represents the residual graph associated with the maximum matching corresponding to the assignment $A=1$, $B=2$, $C=3$, $D=4$, $E=5$, $F=6$, $G=7$, $H=8$. It has four strongly connected components containing respectively vertices $\left\{A,B,1,2\right\}$, $\left\{C,D,3,4\right\}$, $\left\{E,F,5,6\right\}$ and $\left\{G,H,7,8\right\}$. Arcs that are between strongly connected components correspond to values that can be removed:

• The removal of value 2 from variable $C$ is explained by the absence of the arcs corresponding to the assignments $A=3$, $A=4$, $B=3$ and $B=4$ (since adding any of these missing arcs would merge the blue and the pink strongly connected components containing the vertices corresponding to value 2 and variable $C$).

• The removal of value 6 from variable $C$ is explained by the absence of the arcs corresponding to the assignments $E=3$, $E=4$, $F=3$ and $F=4$. Again adding the corresponding arcs would merge the two strongly connected components containing the vertices corresponding to value 6 and variable $C$.

• The removal of value 6 from variable $G$ is explained by the absence of the arcs corresponding to the assignments $E=7$, $E=8$, $F=7$ and $F=8$.

• The removal of value 6 from variable $H$ is explained by the absence of the arcs corresponding to the assignments $E=7$, $E=8$, $F=7$ and $F=8$.

After applying bound-consistency the following property holds for all variables of an $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint. Given a Hall interval $\left[l,u\right]$, any variable $V$ whose range $\left[\underset{Μ²}{V},\stackrel{Β―}{V}\right]$ intersects $\left[l,u\right]$ without being included in $\left[l,u\right]$ has its minimum value $\underset{Μ²}{V}$ (respectively maximum value $\stackrel{Β―}{V}$) that is located before (respectively after) the Hall interval (i.e.,Β $\underset{Μ²}{V}).

The $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint is entailed if and only if there is no value $v$ that can be assigned two distinct variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection (i.e.,Β the intersection of the two sets of potential values of any pair of variables is empty).

Reformulation

The $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint can be reformulated into a set of disequalities constraints. This model neither preserves bound-consistency nor arc-consistency:

• On the one hand a model, involving linear constraints, preserving bound-consistency was introduced inΒ [BessiereKatsirelosNarodytskaQuimperWalsh09IJCAI]. For each potential interval $\left[l,u\right]$ of consecutive values this model uses $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$ 0-1 variables ${B}_{1,l,u},{B}_{2,l,u},...,{B}_{|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|,l,u}$ for modelling the fact that each variable of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ is assigned a value within interval $\left[l,u\right]$ (i.e.,Β $\beta i\beta \left[1,|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|\right]:{B}_{i,l,u}\beta \mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\left[i\right].\mathrm{\pi \pi \pi }\beta \left[l,u\right]$),How to encode the reified constraint ${B}_{i,l,u}\beta \mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\left[i\right].\mathrm{\pi \pi \pi }\beta \left[l,u\right]$ with linear constraints is described in the Reformulation slot of the $\mathrm{\pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint. and an inequality constraint for enforcing the condition that the sum of the corresponding 0-1 variables is less than or equal to the size $u-l+1$ of the corresponding interval (i.e.Β ${B}_{1,l,u}+{B}_{2,l,u}+...+{B}_{|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|,l,u}\beta €u-l+1$).

• On the other hand, it was shown inΒ [BessiereKatsirelosNarodytskaWalsh09] that there is no polynomial sized decomposition that preserves arc-consistency.

Systems
Used in

generalisation: $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi }\mathrm{\pi \pi \pi \pi \pi \pi \pi }$, all of the same size), Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi }\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$), $\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 }+\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$), $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }/\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$), $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\mathrm{mod}\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$), $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\beta \mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }$), $\mathrm{\pi \pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by orthotope), $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi }$), $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi ’}$Β (control the number of occurrence of each value with a counter variable), Β (control the number of occurrence of each value with an interval), $\mathrm{\pi \pi \pi ‘}_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi \pi \pi }$), $\mathrm{\pi \pi \pi \pi \pi \pi }$Β (count number of distinct values).

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 \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 }$
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 an equality constraint between each pair of vertices (including a vertex and itself) and state that the size of the largest strongly connected component should not exceed one.

PartsΒ (A) andΒ (B) of FigureΒ 5.5.3 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 component of the final graph. The $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ holds since all the strongly connected components have at most one vertex: a value is used at most once.

Automaton

FigureΒ 5.5.4 depicts the automaton associated with the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint. To each item of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ corresponds a signature variable ${\mathrm{\pi }}_{i}$ that is equal to 1. The automaton counts the number of occurrences of each value and finally imposes that each value is taken at most one time.