5.171. k_alldifferent
| DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
k_alldifferent(VARS)
- Synonym(s)
- Type(s)
-
X collection(x−dvar) - Argument(s)
-
VARS collection(vars−X) - Restriction(s)
-
required(X,x) required(VARS,vars) |X|>0 |VARS|>0 - Purpose
For each collection of variables depicted by an item of VARS, enforce their corresponding variables to take distinct values.
- Example
-
(
)〈
〉vars−〈5,6,0,9,3〉, vars−〈5,6,1,2〉 The k_alldifferent constraint holds since all the values 5, 6, 0, 9 and 3 are distinct and since all the values 5, 6, 1 and 2 are distinct as well.
- Usage
Systems of alldifferent constraints sharing variables occurs frequently in practice. We give 4 typical problems that can be modelled by a combination of alldifferent constraints as well as one problem where a system of alldifferent constraints provides a necessary condition.
The graph colouring problem is to colour with a restricted number of colours the vertices of a given undirected graph in such a way that adjacent vertices are coloured with distinct colours. The problem can be modelled by a system of alldifferent constraints. All the next problems can been seen as graph colouring problems where the graphs have some specific structure.
A latin square of order n is an n×n array in which n distinct numbers in [1,n] are arranged so that each number occurs once in each row and column. The problem is to complete a partially filled latin square. Part (A) of Figure 5.171.1 gives a partially filled latin square, while part (B) provides a possible completion.
Figure 5.171.1. A partially filled latin square and a possible completion
A Sudoku is a latin square of order 9×9 such that the numbers in each major 3×3 block are distinct. As for the latin square problem, the problem is to complete a partially filled board. Part (A) of Figure 5.171.2 gives a partially filled Sudoku board, while part (B) provides a possible completion. A constraint programming approach for solving Sudoku puzzles is depicted in [Simonis05]. It shows how to generate redundant constraints as well as shaving [MartinShmoys96] in order to find a solution without guessing.
Figure 5.171.2. A partially Sudoku square and a possible completion
A task assignment problem consists to assign a given set of non -preemptive tasks, which are fixed in time (i.e., the origin, duration and end of each task are fixed), to a set of resources so that, tasks that are assigned to the same resource do not overlap in time. Each task can be assigned to a predefined set of resources. Problems like aircraft stand allocation [DincbasSimonis91], [Simonis01] or air traffic flow management [BarnierBrisset02] correspond to an example of a real -life task assignment problem.
Part (A) of Figure 5.171.3 gives an example of task assignment problem. For each task we indicate the set of resources where it can potentially be assigned (i.e., the domain of its assignment variable). For instance, task T1 can be assigned to resources 1 or 2. Part (B) of Figure 5.171.3 gives the corresponding interval graph: We have one vertex for each task and an edge between two tasks that overlap in time. We have a system of alldifferent constraints corresponding to the maximum cliques of the interval graph (i.e., {T1,T5,T8}, {T2,T5,T8}, {T2,T6}, {T3,T6,T9}, {T3,T7,T9}, {T4,T7,T9}). Finally, part (C) of Figure 5.171.3 provides a possible solution to the task assignment problem where tasks T1, T2, T9 are assigned to resource 1, tasks T3, T4, T8 are assigned to resource 2, and tasks T5, T6, T7 are assigned to resource 3.
Figure 5.171.3. A task assignment problem, its corresponding interval graph and a possible solution
The tree partitioning with precedences problem is to compute a vertex -partitioning of a given digraph G in disjoint trees (i.e., a forest), so that a given set of precedences holds. The problem can be modelled with a tree_precedence(NTREE,VERTICES) constraint, where NTREE is a domain variable specifying the numbers of trees in the forest and VERTICES is a collection of the digraph's n vertices. Each item v∈VERTICES has the following attributes, which complete the description of the digraph:
index is an integer in [1,n] that can be interpreted as the label of v.
father is a domain variable whose domain consists of elements (vertex label) of [1,n]. It can be interpreted as the unique successor of v.
preds is a possibly empty set of integers, its elements (vertex label) being in [1,n]. It can be interpreted as the mandatory ancestors of v.
We model the tree_precedence constraint by the digraph G=(V,E) in which the vertices represent the elements of VERTICES and the arcs represent the successors relations between them. Formally, G is defined as follows:
To the ith vertex (1≤i≤n), VERTICES[i], of the VERTICES collection corresponds a vertex of V denoted by vi.
For every pair of vertices (VERTICES[i],VERTICES[j]), where i and j are not necessarily distinct, there is an arc from vi to vj in E.
The tree_precedence constraint specifies that its associated digraph G should be a forest that fulfils the precedence constraints. Formally a ground instance of a tree_precedence(NTREE,VERTICES) constraint is satisfied if and only if the following conditions hold:
∀i∈[1,n]:VERTICES[i].index=i,
Its associated digraph G consists of NTREE connected components,
Each connected component of G does not contain any circuit involving more than one vertex,
For every vertex VERTICES[i] such that j∈VERTICES[i].preds there must be an elementary path in G from VERTICES[j] to VERTICES[i].
We can build the following system of alldifferent constraints that corresponds to a necessary condition for the tree_precedence constraint: To each vertex v of G, which both has no predecessors and cannot be the root of a tree, we generate an alldifferent constraint involving the father variables of those descendants of v in G that cannot be the root of a tree.
Figure 5.171.4. A set of precedences and a corresponding feasible tree
For the set of precedences depicted by part (A) of Figure 5.171.4The number in a vertex gives the value of the index attribute of the corresponding item., where we assume that VERTICES[12] is the only vertex that can be a root and where Fi denotes the father variable associated with VERTICES[i], we get the following system of alldifferent constraints:
alldifferent(〈F1,F3,F5,F6,F7,F10,F11〉),
alldifferent(〈F2,F4,F7,F8,F9,F10,F11〉).
The variables of these two alldifferent constraints respectively correspond to the descendants of the two source vertices (i.e., F1 and F2) of the precedence graph depicted by part (A) of Figure 5.171.4. On part (A) of Figure 5.171.4 the descendants of F1 and F2 are respectively depicted with a thick line and a grey circle. Their intersection, {F7,F10,F11,F12}, from which we remove F12 belong to the two alldifferent constraints. In fact, F12 is not mentioned in the two alldifferent constraints since its corresponding vertex is the root of a tree. Part (B) of Figure 5.171.4 gives a possible tree satisfying all the precedences constraints expressed by part (A), where precedences are depicted with a dotted line. It corresponds to the following ground solution:
- Remark
It was shown in [ElbassioniKatrielKutzMahajan05b] that, finding out whether a system of two alldifferent constraints sharing some variables has a solution or not is NP -hard. This was achieved by reduction from set packing.
A slight variation in the way of describing the arguments of the k_alldifferent constraint appears in [RichterFreundNaveh06] under the name of some_different: the set of disequalities is described by a set of pairs of variables, where each pair corresponds to a disequality constraint between two given variables.
Within the context of linear programming, a relaxation of the k_alldifferent constraint is provided in [AppaMagosMourtos04]. The special case where k=2 is discussed in [AppaMagosMourtos05].
- Algorithm
Even if there is no filtering algorithm for the k_alldifferent constraint, one can enforce redundant constraints for the following patterns:
Within the context of graph colouring, one can state an nvalue constraint for every cycle of odd length of the graph to colour enforcing that the corresponding variables have to be assigned to at least three distinct values.
Within the context of latin squares, one can state a colored_matrix constraint enforcing that each value is used exactly once in each row and column.
Within the context of two alldifferent constraints alldifferent(〈U1,...,Un,V1,...,Vm〉) and alldifferent(〈U1,...,Un, W1,...,Wm〉) where the domain of all variables U1,...,Un, V1,...,Vm, W1,...,Wm is included in the interval [1,n+m], one can state a same_and_global_cardinality constraint stating that the variables V1,...,Vm should correspond to a permutation of the variables W1,...,Wm and that the variables V1,...,Vm should be assigned to distinct values.
In the general case of two alldifferent constraints alldifferent(〈U1,...,Un,V1,...,Vm〉) and alldifferent(〈U1,...,Un, W1,...,Wo〉), one can state an nvalue constraint involving the variables V1,...,Vm and W1,...,Wo enforcing that these variables should not use more than s−n distinct values, where s denotes the cardinality of the union of the domains of the variables U1,...,Un, V1,...,Vm, W1,...,Wo.
Several propagation rules for the k_alldifferent constraint are also described in [LardeuxMonfroySaubion08].
- See also
alldifferent, colored_matrix, same_and_global_cardinality, nvalue.
- Key words
application area: air traffic management, assignment.
characteristic of a constraint: all different, disequality.
combinatorial object: permutation, latin square.
constraint type: system of constraints, overlapping alldifferent, value constraint, decomposition.
For all items of VARS:
- Arc input(s)
-
VARS.vars - Arc generator
-
CLIQUE↦collection(x1,x2) - Arc arity
-
2 - Arc constraint(s)
-
x1.x=x2.x - Graph property(ies)
-
MAX_NSCC≤1
- Graph model
For each collection of variables depicted by an item of VARS 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.