[Lauriere78]

$\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

$\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏}$, $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$, $\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$, $\mathrm{𝚋𝚘𝚞𝚗𝚍}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$, $\mathrm{𝚋𝚘𝚞𝚗𝚍}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏}$, $\mathrm{𝚋𝚘𝚞𝚗𝚍}\_\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$, $\mathrm{𝚛𝚎𝚕}$.

The $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint holds since all the values 5, 1, 9 and 3 are distinct.

Figure 5.12.1 gives all solutions to the following non ground instance of the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint: $V_1\in [2,4]$, $V_2\in [2,3]$, $V_3\in [1,6]$, $V_4\in [2,5]$, $V_5\in [2,3]$, $V_6\in [1,6]$, $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$\left(\langle V_1,V_2,V_3,V_4,V_5,V_6\rangle \right)$.

Figure 5.12.1. All solutions corresponding to the non ground example of the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint of the All solutions slot

• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are permutable.

• Two distinct values of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ can be swapped; a value of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ can be renamed to any unused value.

Contractible wrt. $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

The $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint occurs in most practical problems directly or indirectly. A classical example is the n-queens chess puzzle problem: Place $n$ queens on an $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{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints. We associate to column $i$ of the chessboard a domain variable $X_i$ that gives the row number where the corresponding queen is located. The three $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints are:

• $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}(X_1,X_2+1,\cdots ,X_n+n-1)$ for the descending diagonals,

• $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}(X_1,X_2,\cdots ,X_n)$ for the rows,

• $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}(X_1+n-1,X_2+n-2,\cdots ,X_n)$ for the ascending diagonals.

They are respectively depicted by parts (A), (C) and (D) of Figure 5.12.2. Figure 5.12.3 makes explicit the link between the two families of diagonals and the corresponding $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints. Note that this model matches the checker introduced by Gauss to test whether a permutation of row numbers is a solution or not to the 8 queens problem: first add the numbers 1 up to 8 to the permutation and check that the resulting numbers are distinct, second add the numbers 8 down to 1 and perform the same check [Watkins04].

Figure 5.12.2. Descending diagonals (A-B), rows (C) and ascending diagonals (D-E)

Figure 5.12.3. (A) For every pair of columns $i$, $j$ ($i<j$), given the position $X_i$ of the queen on column $i$, we respectively have from the ascending and descending diagonals that $X_j\ne X_i+(j-i)$ and $X_j\ne X_i-(j-i)$ (B) Equivalence of the two $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints respectively associated with the ascending and descending diagonals with the two families of disequalities (i.e., the orange and the red one) depicted in Part (A)

A second example taken from [AsratianDenleyHaggkvist98], where the bipartite graph associated with the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint is convex, is a ski assignment problem: “a set of skiers have each specified the smallest and largest ski sizes they will accept from a given set of ski sizes”. The task is to find a ski size for each skier.

Examples such as Costas arrays and Golomb rulers involve one or several $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints on differences of variables.

Quite often, the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint is also used in conjunction with several $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraints, especially in the context of assignment problems [Hooker07book], or with several precedence constraints, especially in the context of symmetry breaking or scheduling problems [BessiereNarodytskaQuimperWalsh11].

Other examples involving several $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints sharing some variables can be found in the Usage slot of the $𝚔\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint.

Even if the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint did not have this form, it was specified in ALICE [Lauriere76], [Lauriere78] by asking for an injective correspondence $f$ between variables and values: $x\ne y\Rightarrow f\left(x\right)\ne f\left(y\right)$. From an algorithmic point of view, the algorithm for computing the cardinality of the maximum matching of a bipartite graph was not used in ALICE for checking the feasibility of the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint, even though the algorithm was already known in 1976. This is because 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 that specialised algorithms should be discarded. On the one hand, many people, especially from the OR community, have complained about such a radical statement [Roy06]. On the other hand, the motivation of such a 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 principles. 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], [EppsteinStrash11] from a set of binary disequalities in order to replace them by $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints.

W.-J. van Hoeve provides a survey about the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint in [Hoeve01].

For possible relaxation of the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints see the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚎𝚡𝚌𝚎𝚙𝚝}\_\mathtt{0}$, the $𝚔\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ (i.e., $\mathrm{𝚜𝚘𝚖𝚎}\_\mathrm{𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$), the $\mathrm{𝚜𝚘𝚏𝚝}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚌𝚝𝚛}$, the $\mathrm{𝚜𝚘𝚏𝚝}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚟𝚊𝚛}$ and the $\mathrm{𝚠𝚎𝚒𝚐𝚑𝚝𝚎𝚍}\_\mathrm{𝚙𝚊𝚛𝚝𝚒𝚊𝚕}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏}$ constraints, and Figure 2.1.4 of Section 2.1.5.

Within the context of linear programming, relaxations of the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ 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{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ 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 $[1,n]$, the total number of solutions to the corresponding $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint corresponds to the sequence A000142 of the On-Line Encyclopaedia of Integer Sequences [Sloane10].

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]. Similarly, Dulmage-Mendelsohn decomposition [DulmageMendelsohn58] was also used recently by [Cymer12], [CymerPhD13] to characterise such edges and prune the corresponding variables both for the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint and for other constraints like $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚎𝚡𝚌𝚎𝚙𝚝}\_\mathtt{0}$, $\mathrm{𝚌𝚘𝚛𝚛𝚎𝚜𝚙𝚘𝚗𝚍𝚎𝚗𝚌𝚎}$, $\mathrm{𝚒𝚗𝚟𝚎𝚛𝚜𝚎}$, $\mathrm{𝚜𝚊𝚖𝚎}$, $\mathrm{𝚞𝚜𝚎𝚍}\_\mathrm{𝚋𝚢}$, $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚕𝚘𝚠}\_\mathrm{𝚞𝚙}$, $\mathrm{𝚜𝚘𝚏𝚝}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚟𝚊𝚛}$, $\mathrm{𝚜𝚘𝚏𝚝}\_\mathrm{𝚜𝚊𝚖𝚎}\_\mathrm{𝚟𝚊𝚛}$, $\mathrm{𝚜𝚘𝚏𝚝}\_\mathrm{𝚞𝚜𝚎𝚍}\_\mathrm{𝚋𝚢}\_\mathrm{𝚟𝚊𝚛}$. 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{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint), which appears to be the main bottleneck in practice. Figures 2.1.1 and 2.1.2 of Section 2.1.3 illustrate the filtering of the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint with respect to arc-consistency and bound-consistency. The leftmost part of Figure 3.7.28 illustrates a flow model for the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint where there is a one-to-one correspondence between feasible flows in the flow model and solutions of the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint.

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(nlogn)$ in [Puget98], [MehlhornThiel00], [LopezOrtizQuimperTrompBeek03]. If sort can be achieved in linear time, typically when the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint encodes a permutation,In this context the total number of values that can be assigned to the variables of the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ 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{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ 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{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint), the removal of an arc starting from a vertex belonging to a strongly connected component ${𝒞}_1$ to a distinct strongly connected component ${𝒞}_2$ is explained by all missing arcs starting from a descendant component of ${𝒞}_2$ and ending in an ancestor component of ${𝒞}_1$ (i.e., since the addition of any of these missing arcs would merge the strongly connected components ${𝒞}_1$ and ${𝒞}_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\in \{1,2\}$, $B\in \{1,2\}$, $C\in \{2,3,4,6\}$, $D\in \{3,4\}$, $E\in \{5,6\}$, $F\in \{5,6\}$, $G\in \{6,7,8\}$, $H\in \{6,7,8\}$. Figure 5.12.4 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 $\{A,B,1,2\}$, $\{C,D,3,4\}$, $\{E,F,5,6\}$ and $\{G,H,7,8\}$. 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$.

Figure 5.12.4. Strongly connected components of the residual graph illustrating the explanation of the removal of a value for the constraint $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$(\langle A,B,C,D,E,F,G,H\rangle )$, $A\in \{1,2\}$, $B\in \{1,2\}$, $C\in \{2,3,4,6\}$, $D\in \{3,4\}$, $E\in \{5,6\}$, $F\in \{5,6\}$, $G\in \{6,7,8\}$, $H\in \{6,7,8\}$: the explanation why value 2 is removed from variable $C$ corresponds to all missing arcs whose addition would merge the blue and the pink strongly connected components (i.e., the missing arcs corresponding to the assignments $A=3$, $A=4$, $B=3$ and $B=4$ that are depicted by thick pink lines)

An additional example for illustrating the generation of explanations for the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint when there are more values than variables is provided by Figure 2.1.3 of Section 2.1.4.

After applying bound-consistency the following property holds for all variables of an $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint. Given a Hall interval $[l,u]$, any variable $V$ whose range $[\underline{V},\overline{V}]$ intersects $[l,u]$ without being included in $[l,u]$ has its minimum value $\underline{V}$ (respectively maximum value $\overline{V}$) that is located before (respectively after) the Hall interval (i.e., $\underline{V}<l\le u<\overline{V}$).

The $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint is entailed if and only if there is no value $v$ that can be assigned two distinct variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection (i.e., the intersection of the two sets of potential values of any pair of variables is empty).

The $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ 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 $[l,u]$ of consecutive values this model uses $\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|$ 0-1 variables $B_{1,l,u},B_{2,l,u},\cdots ,B_{\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|,l,u}$ for modelling that each variable of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ is assigned a value within interval $[l,u]$ (i.e., $\forall i\in [1,|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\left|\right]:B_{i,l,u}\iff \mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\left[i\right].\mathrm{𝚟𝚊𝚛}\in [l,u]$),How to encode the reified constraint $B_{i,l,u}\iff \mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\left[i\right].\mathrm{𝚟𝚊𝚛}\in [l,u]$ with linear constraints is described in the Reformulation slot of the $\mathrm{𝚒𝚗}\_\mathrm{𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕}\_\mathrm{𝚛𝚎𝚒𝚏𝚒𝚎𝚍}$ 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}+\cdots +B_{\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|,l,u}\le u-l+1$).

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

Finally the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$ constraint can also be reformulated as the conjunction $\mathrm{𝚜𝚘𝚛𝚝}$$(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚂𝙾𝚁𝚃𝙴𝙳}\_\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂})\wedge$ $\mathrm{𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢}\_\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}$$(\mathrm{𝚂𝙾𝚁𝚃𝙴𝙳}\_\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂})$. Unlike the naive reformulation, i.e., a $\mathrm{𝚍𝚒𝚜𝚎𝚚𝚞𝚊𝚕𝚒𝚝𝚢}$ constraint between each pair of variables, the $\mathrm{𝚜𝚘𝚛𝚝}$-based reformulation is linear in space.

Number of solutions for $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$: domains $0..n$

allDifferent in Choco, linear in Gecode, alldifferent in JaCoP, alldiff in JaCoP, alldistinct in JaCoP, all_different in MiniZinc, all_different in SICStus, all_distinct in SICStus.

$\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}\_\mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}$, $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}\_\mathrm{𝚌𝚕𝚞𝚜𝚝𝚎𝚛}$, $\mathrm{𝚌𝚘𝚛𝚛𝚎𝚜𝚙𝚘𝚗𝚍𝚎𝚗𝚌𝚎}$, $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}\_\mathrm{𝚌𝚘𝚗𝚟𝚎𝚡}$, $\mathrm{𝚖𝚊𝚡}\_\mathrm{𝚘𝚌𝚌}\_\mathrm{𝚘𝚏}\_\mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}\_\mathrm{𝚝𝚞𝚙𝚕𝚎𝚜}\_\mathrm{𝚘𝚏}\_\mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}$, $\mathrm{𝚖𝚊𝚡}\_\mathrm{𝚘𝚌𝚌}\_\mathrm{𝚘𝚏}\_\mathrm{𝚜𝚘𝚛𝚝𝚎𝚍}\_\mathrm{𝚝𝚞𝚙𝚕𝚎𝚜}\_\mathrm{𝚘𝚏}\_\mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}$, $\mathrm{𝚜𝚒𝚣𝚎}\_\mathrm{𝚖𝚊𝚡}\_\mathrm{𝚜𝚎𝚚}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$, $\mathrm{𝚜𝚒𝚣𝚎}\_\mathrm{𝚖𝚊𝚡}\_\mathrm{𝚜𝚝𝚊𝚛𝚝𝚒𝚗𝚐}\_\mathrm{𝚜𝚎𝚚}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$, $\mathrm{𝚜𝚘𝚛𝚝}\_\mathrm{𝚙𝚎𝚛𝚖𝚞𝚝𝚊𝚝𝚒𝚘𝚗}$.

common keyword: $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$, $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}\_\mathrm{𝚌𝚕𝚞𝚜𝚝𝚎𝚛}$, $\mathrm{𝚌𝚢𝚌𝚕𝚎}$, $\mathrm{𝚍𝚎𝚛𝚊𝚗𝚐𝚎𝚖𝚎𝚗𝚝}$ (permutation), $\mathrm{𝚐𝚘𝚕𝚘𝚖𝚋}$ (all different), $\mathrm{𝚙𝚛𝚘𝚙𝚎𝚛}\_\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ (permutation), $\mathrm{𝚜𝚒𝚣𝚎}\_\mathrm{𝚖𝚊𝚡}\_\mathrm{𝚜𝚎𝚚}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$, $\mathrm{𝚜𝚒𝚣𝚎}\_\mathrm{𝚖𝚊𝚡}\_\mathrm{𝚜𝚝𝚊𝚛𝚝𝚒𝚗𝚐}\_\mathrm{𝚜𝚎𝚚}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ (all different,disequality), $\mathrm{𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ (permutation).

cost variant: $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}\_\mathrm{𝚠𝚎𝚒𝚐𝚑𝚝}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$, $\mathrm{𝚠𝚎𝚒𝚐𝚑𝚝𝚎𝚍}\_\mathrm{𝚙𝚊𝚛𝚝𝚒𝚊𝚕}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏}$.

generalisation: $\mathrm{𝚊𝚕𝚕}\_\mathrm{𝚖𝚒𝚗}\_\mathrm{𝚍𝚒𝚜𝚝}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by $\mathrm{𝚕𝚒𝚗𝚎}\mathrm{𝚜𝚎𝚐𝚖𝚎𝚗𝚝}$, all of the same size), $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚋𝚎𝚝𝚠𝚎𝚎𝚗}\_\mathrm{𝚜𝚎𝚝𝚜}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by $\mathrm{𝚜𝚎𝚝}\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$), $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚌𝚜𝚝}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}+\mathrm{𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝}$), $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}/\mathrm{𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝}$), $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚖𝚘𝚍𝚞𝚕𝚘}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}\mathrm{mod}\mathrm{𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝}$), $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}\in \mathrm{𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}$), $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by orthotope), $\mathrm{𝚍𝚒𝚜𝚓𝚞𝚗𝚌𝚝𝚒𝚟𝚎}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by $\mathrm{𝚝𝚊𝚜𝚔}$), $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ (control the number of occurrence of each value with a counter variable), $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚕𝚘𝚠}\_\mathrm{𝚞𝚙}$ (control the number of occurrence of each value with an interval), $\mathrm{𝚕𝚎𝚡}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by $\mathrm{𝚟𝚎𝚌𝚝𝚘𝚛}$), $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ (count number of distinct values).

implied by: $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}\_\mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}$, $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$, $\mathrm{𝚌𝚢𝚌𝚕𝚎}$, $\mathrm{𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢}\_\mathrm{𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}$, $\mathrm{𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢}\_\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}$.

implies: $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚎𝚡𝚌𝚎𝚙𝚝}\_\mathtt{0}$, $\mathrm{𝚖𝚞𝚕𝚝𝚒}\_\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚘𝚗𝚝𝚒𝚐𝚞𝚒𝚝𝚢}$, $\mathrm{𝚗𝚘𝚝}\_\mathrm{𝚊𝚕𝚕}\_\mathrm{𝚎𝚚𝚞𝚊𝚕}$.

negation: $\mathrm{𝚜𝚘𝚖𝚎}\_\mathrm{𝚎𝚚𝚞𝚊𝚕}$.

part of system of constraints: $\mathrm{𝚗𝚎𝚚}$.

shift of concept: $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚘𝚗}\_\mathrm{𝚒𝚗𝚝𝚎𝚛𝚜𝚎𝚌𝚝𝚒𝚘𝚗}$, $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚜𝚊𝚖𝚎}\_\mathrm{𝚟𝚊𝚕𝚞𝚎}$.

soft variant: $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚎𝚡𝚌𝚎𝚙𝚝}\_\mathtt{0}$ (value 0 can be used several times), $\mathrm{𝚘𝚙𝚎𝚗}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ (open constraint), $\mathrm{𝚜𝚘𝚏𝚝}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚌𝚝𝚛}$ (decomposition-based violation measure), $\mathrm{𝚜𝚘𝚏𝚝}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚟𝚊𝚛}$ (variable-based violation measure).

system of constraints: $𝚔\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$.

used in reformulation: $\mathrm{𝚒𝚗}\_\mathrm{𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕}\_\mathrm{𝚛𝚎𝚒𝚏𝚒𝚎𝚍}$ (bound-consistency preserving reformulation), $\mathrm{𝚜𝚘𝚛𝚝}$, $\mathrm{𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢}\_\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}$.

uses in its reformulation: $\mathrm{𝚌𝚢𝚌𝚕𝚎}$, $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚜}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$, $\mathrm{𝚜𝚘𝚛𝚝}\_\mathrm{𝚙𝚎𝚛𝚖𝚞𝚝𝚊𝚝𝚒𝚘𝚗}$.

characteristic of a constraint: core, all different, disequality, sort based reformulation, automaton, automaton with array of counters.

combinatorial object: permutation.

constraint type: system of constraints, value constraint.

filtering: bipartite matching, bipartite matching in convex bipartite graphs, convex bipartite graph, flow, Hall interval, arc-consistency, bound-consistency, SAT, DFS-bottleneck, entailment.

final graph structure: one_succ.

modelling exercises: n-Amazons, zebra puzzle.

problems: maximum clique, graph colouring.

puzzles: n-Amazons, n-queens, Costas arrays, Euler knight, Golomb ruler, magic hexagon, magic square, zebra puzzle, Sudoku.