5.175. k_alldifferent

DESCRIPTIONLINKSGRAPH
Origin

[ElbassioniKatrielKutzMahajan05]

Constraint

πš”_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(πš…π™°πšπš‚)

Synonyms

πš”_πšŠπš•πš•πšπš’πšπš, πš”_πšŠπš•πš•πšπš’πšœπšπš’πš—πšŒπš, πšœπš˜πš–πšŽ_πšπš’πšπšπšŽπš›πšŽπš—πš.

Type
πš‡πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚑-πšπšŸπšŠπš›)
Argument
πš…π™°πšπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πšœ-πš‡)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš‡,𝚑)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπš‚,πšŸπšŠπš›πšœ)
|πš‡|>0
|πš…π™°πšπš‚|>0
Purpose

For each collection of variables depicted by an item of πš…π™°πšπš‚, enforce their corresponding variables to take distinct values.

Example
πšŸπšŠπš›πšœ-𝚑-5,𝚑-6,𝚑-0,𝚑-9,𝚑-3,πšŸπšŠπš›πšœ-5,6,1,2

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
|πš‡|>1
|πš…π™°πšπš‚|>1
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.

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 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.175.1 gives a partially filled Latin square, while partΒ (B) provides a possible completion.

    Figure 5.175.1. A partially filled Latin square and a possible completion
    ctrs/k_alldifferent1
  • 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.175.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.175.2. A partially Sudoku square and a possible completion
    ctrs/k_alldifferent2
  • 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.175.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.175.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.,Β {T1,T5,T8}, {T2,T5,T8}, {T2,T6}, {T3,T6,T9}, {T3,T7,T9}, {T4,T7,T9}). Finally, partΒ (C) of FigureΒ 5.175.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.175.3. A task assignment problem, its corresponding interval graph and a possible solution
    ctrs/k_alldifferent3
  • 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 n vertices. Each item vβˆˆπš…π™΄πšπšƒπ™Έπ™²π™΄πš‚ has the following attributes, which complete the description of the digraph:

    • πš’πš—πšπšŽπš‘ is an integer in [1,n] that can be interpreted as the label of v.

    • πšπšŠπšπš‘πšŽπš› is a domain variable whose domain consists of elements (vertex label) of [1,n]. It can be interpreted as the unique successor of v.

    • πš™πš›πšŽπšπšœ 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 πšπš›πšŽπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽπš—πšŒπšŽ 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 i th vertex (1≀i≀n), πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚[i], of the πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚ collection corresponds a vertex of 𝒱 denoted by v i .

    • For every pair of vertices (πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚[i],πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚[j]), where i and j are not necessarily distinct, there is an arc from v i to v j 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:

    1. βˆ€i∈[1,n]:πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚[i].πš’πš—πšπšŽπš‘=i,

    2. Its associated digraph 𝒒 consists of π™½πšƒπšπ™΄π™΄ connected components,

    3. Each connected component of 𝒒 does not contain any circuit involving more than one vertex,

    4. For every vertex πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚[i] such that jβˆˆπš…π™΄πšπšƒπ™Έπ™²π™΄πš‚[i].πš™πš›πšŽπšπšœ there must be an elementary path in 𝒒 from πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚[j] to πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚[i].

    We can build the following system of πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraints that corresponds to a necessary condition for the πšπš›πšŽπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽπš—πšŒπšŽ constraint: To each vertex v 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 v in 𝒒 that cannot be the root of a tree.

    Figure 5.175.4. A set of precedences and a corresponding feasible tree
    ctrs/k_alldifferent4

    For the set of precedences depicted by partΒ (A) of FigureΒ 5.175.4The number in a vertex gives the value of the πš’πš—πšπšŽπš‘ attribute of the corresponding item., where we assume that πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚[12] is the only vertex that can be a root and where F i denotes the father variable associated with πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚[i], 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.,Β F 1 and F 2 ) of the precedence graph depicted by partΒ (A) of FigureΒ 5.175.4. On partΒ (A) of FigureΒ 5.175.4 the descendants of F 1 and F 2 are respectively depicted with a thick line and a grey circle. Their intersection, {F 7 ,F 10 ,F 11 ,F 12 }, from which we remove F 12 belong to the two πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraints. In fact, F 12 is not mentioned in the two πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraints since its corresponding vertex is the root of a tree. PartΒ (B) of FigureΒ 5.175.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:

    πšπš›πšŽπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽπš—πšŒπšŽ(βŒ©πš’πš—πšπšŽπš‘-1πšπšŠπšπš‘πšŽπš›-3πš™πš›πšŽπšπšœ-{},
    Β πš’πš—πšπšŽπš‘-2πšπšŠπšπš‘πšŽπš›-4πš™πš›πšŽπšπšœ-{},
    Β πš’πš—πšπšŽπš‘-3πšπšŠπšπš‘πšŽπš›-5πš™πš›πšŽπšπšœ-{1},
    Β πš’πš—πšπšŽπš‘-4πšπšŠπšπš‘πšŽπš›-8πš™πš›πšŽπšπšœ-{2},
    Β πš’πš—πšπšŽπš‘-5πšπšŠπšπš‘πšŽπš›-6πš™πš›πšŽπšπšœ-{1},
    Β πš’πš—πšπšŽπš‘-6πšπšŠπšπš‘πšŽπš›-7πš™πš›πšŽπšπšœ-{3},
    Β πš’πš—πšπšŽπš‘-7πšπšŠπšπš‘πšŽπš›-10πš™πš›πšŽπšπšœ-{3,4},
    Β πš’πš—πšπšŽπš‘-8πšπšŠπšπš‘πšŽπš›-9πš™πš›πšŽπšπšœ-{4},
    Β πš’πš—πšπšŽπš‘-9πšπšŠπšπš‘πšŽπš›-7πš™πš›πšŽπšπšœ-{2},
    Β πš’πš—πšπšŽπš‘-10πšπšŠπšπš‘πšŽπš›-11πš™πš›πšŽπšπšœ-{5,6,7},
    Β πš’πš—πšπšŽπš‘-11πšπšŠπšπš‘πšŽπš›-12πš™πš›πšŽπšπšœ-{7,8,9},
    Β πš’πš—πšπšŽπš‘-12πšπšŠπšπš‘πšŽπš›-12πš™πš›πšŽπšπšœ-{10,11} βŒͺ)
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 k=2 is discussed inΒ [AppaMagosMourtos05].

Algorithm

Even if there is no filtering algorithm for the πš”_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint, one can enforce redundant constraints for the following patterns:

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.

complexity: set packing.

constraint type: system of constraints, overlapping alldifferent, value constraint, decomposition.

filtering: bound-consistency, duplicated variables.

problems: graph colouring.

puzzles: Sudoku.

For all items of πš…π™°πšπš‚:

Arc input(s)
πš…π™°πšπš‚.πšŸπšŠπš›πšœ
Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚑1,𝚑2)

Arc arity
Arc constraint(s)
𝚑1.𝚑=𝚑2.𝚑
Graph property(ies)
πŒπ€π—_𝐍𝐒𝐂𝐂≀1

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.