5.204. k_alldifferent
DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Synonyms
, , .
- Type
- Argument
- Restrictions
- Purpose
For each collection of variables depicted by an item of , enforce their corresponding variables to take distinct values. Usually some variables occur in several collections.
- Example
-
The 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.
- Typical
- Symmetries
Items of are permutable.
Items of are permutable.
All occurrences of two distinct values of can be swapped; all occurrences of a value of can be renamed to any unused value.
- Arg. properties
Contractible wrt. .
- Usage
Systems of constraints sharing variables occurs frequently in practice. We give 4 typical problems that can be modelled by a combination of constraints as well as one problem where a system of 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 constraints. All the next problems can been seen as graph colouring problems where the graphs have some specific structure.
A Latin square of order is an array in which distinct numbers in 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.204.1 gives a partially filled Latin square, while partΒ (B) provides a possible completion.
Figure 5.204.1. (A)Β A partially filled Latin square and (B)Β a possible completion
A Sudoku is a Latin square of order such that the numbers in each major block are distinct. As for the Latin square problem, the problem is to complete a partially filled board. PartΒ (A) of FigureΒ 5.204.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.204.2. (A)Β A partially filled Sudoku square and (B)Β its unique 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. Assignment of service professionalsΒ [AsafEranRichterConnorsGreshOrtegaMcinnis10] is yet another industrial example where professionals have to be assigned positions in such a way that positions assigned to a given professional do not overlap in time.
PartΒ (A) of FigureΒ 5.204.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 can be assigned to resources 1 or 2. PartΒ (B) of FigureΒ 5.204.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 constraints corresponding to the maximum cliques of the interval graph (i.e.,Β , , , , , ). Finally, partΒ (C) of FigureΒ 5.204.3 provides a possible solution to the task assignment problem where tasks , , are assigned to resource 1, tasks , , are assigned to resource 2, and tasks , , are assigned to resource 3.
Figure 5.204.3. (A)Β Tasks with their potential assignment 1, 2 or 3 (B)Β Interval graph where to each task of corresponds a vertex, and to each pair of overlapping tasks corresponds an edge (C)Β A valid assignment where tasks assigned to a same machine do not overlap
The tree partitioning with precedences problem is to compute a vertex-partitioning of a given digraph in disjoint trees (i.e.,Β a forest), so that a given set of precedences holds. The problem can be modelled with a constraint, where is a domain variable specifying the numbers of trees in the forest and is a collection of the digraph's vertices. Each item has the following attributes, which complete the description of the digraph:
is an integer in that can be interpreted as the label of .
is a domain variable whose domain consists of elements (vertex label) of . It can be interpreted as the unique successor of .
is a possibly empty set of integers, its elements (vertex label) being in . It can be interpreted as the mandatory ancestors of .
We model the constraint by the digraph in which the vertices represent the elements of and the arcs represent the successors relations between them. Formally, is defined as follows:
To the vertex , , of the collection corresponds a vertex of denoted by .
For every pair of vertices ,, where and are not necessarily distinct, there is an arc from to in .
The constraint specifies that its associated digraph should be a forest that fulfils the precedence constraints. Formally a ground instance of a constraint is satisfied if and only if the following conditions hold:
,
Its associated digraph consists of connected components,
Each connected component of does not contain any circuit involving more than one vertex,
For every vertex such that there must be an elementary path in from to .
We can build the following system of constraints that corresponds to a necessary condition for the constraint: To each vertex of , which both has no predecessors and cannot be the root of a tree, we generate an constraint involving the father variables of those descendants of in that cannot be the root of a tree.
Figure 5.204.4. (A)Β A set of precedences and (D)Β a corresponding feasible tree where stands for the father of the vertex; (B)Β the constraint associated with the source vertex 1 and (E)Β the satisfied precedences in red along the paths of the tree ofΒ (D); (C)Β the constraint associated with the source vertex 2 and (F)Β the satisfied precedences in blue along the paths of the tree ofΒ (D);
For the set of precedences depicted by partΒ (A) of FigureΒ 5.204.4The number in a vertex gives the value of the attribute of the corresponding item., where we assume that is the only vertex that can be a root and where denotes the father variable associated with , we get the following system of constraints:
The variables of these two constraints respectively correspond to the descendants of the two source vertices (i.e.,Β and ) of the precedence graph depicted by partsΒ (B) andΒ (C) of FigureΒ 5.204.4. On partΒ (B) andΒ (C) of FigureΒ 5.204.4 the descendants of and are respectively depicted in red and blue. Their intersection, , from which we remove belong to the two constraints. In fact, is not mentioned in the two constraints since its corresponding vertex is the root of a tree. PartΒ (D) of FigureΒ 5.204.4 gives a possible tree satisfying all the precedences constraints expressed by partΒ (A). It corresponds to the following ground solution:
Β Β Β Β Β Β Β Β Β Β Β PartsΒ (E) andΒ (F) of FigureΒ 5.204.4 illustrate how the precedence constraints are satisfied by the solution depicted by partΒ (D): each precedence, represented by a dashed arc, links two vertices that belong to a same path of the tree that is directed toward the root of the tree.
- Remark
It was shown inΒ [ElbassioniKatrielKutzMahajan05b] that, finding out whether a system of two 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 constraint appears inΒ [RichterFreundNaveh06] under the name of : 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 constraint is provided inΒ [AppaMagosMourtos04]. The special case where is discussed inΒ [AppaMagosMourtos05].
- Algorithm
Even if there is no filtering algorithm for the constraint, one can enforce redundant constraints for the following patterns:
Within the context of graph colouring, one can state an 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 constraint enforcing that each value is used exactly once in each row and column.
Within the context of two constraints and where the domain of all variables , , is included in the interval , one can state a constraint stating that the variables should correspond to a permutation of the variables and that the variables should be assigned to distinct values.
In the general case of two constraints and , one can state an constraint involving the variables and enforcing that these variables should not use more than distinct values, where denotes the cardinality of the union of the domains of the variables , , .
Several propagation rules for the constraint are also described inΒ [LardeuxMonfroySaubion08].
- Reformulation
Given two constraints that share some variables, a reformulation preserving bound-consistency was introduced inΒ [BessiereKatsirelosNarodytskaQuimperWalsh10]. This reformulation is based on an extension of Hall's theorem that is presented in the same paper.
- See also
common keyword: Β (system of constraints).
generalisation: , Β (tasks for which the start attribute is not fixed).
part of system of constraints: .
related: Β (implied by two overlapping ), Β (implied by two overlapping and restriction on values).
- Keywords
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 :
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
For each collection of variables depicted by an item of 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.