5.331. symmetric_alldifferent

DESCRIPTIONLINKSGRAPH
Origin

[Regin99]

Constraint

๐šœ๐šข๐š–๐š–๐šŽ๐š๐š›๐š’๐šŒ_๐šŠ๐š•๐š•๐š๐š’๐š๐š๐šŽ๐š›๐šŽ๐š—๐š(๐™ฝ๐™พ๐™ณ๐™ด๐š‚)

Synonyms

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

Argument
๐™ฝ๐™พ๐™ณ๐™ด๐š‚๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐š’๐š—๐š๐šŽ๐šก-๐š’๐š—๐š,๐šœ๐šž๐šŒ๐šŒ-๐š๐šŸ๐šŠ๐š›)
Restrictions
๐š›๐šŽ๐šš๐šž๐š’๐š›๐šŽ๐š(๐™ฝ๐™พ๐™ณ๐™ด๐š‚,[๐š’๐š—๐š๐šŽ๐šก,๐šœ๐šž๐šŒ๐šŒ])
๐™ฝ๐™พ๐™ณ๐™ด๐š‚.๐š’๐š—๐š๐šŽ๐šกโ‰ฅ1
๐™ฝ๐™พ๐™ณ๐™ด๐š‚.๐š’๐š—๐š๐šŽ๐šกโ‰ค|๐™ฝ๐™พ๐™ณ๐™ด๐š‚|
๐š๐š’๐šœ๐š๐š’๐š—๐šŒ๐š(๐™ฝ๐™พ๐™ณ๐™ด๐š‚,๐š’๐š—๐š๐šŽ๐šก)
๐™ฝ๐™พ๐™ณ๐™ด๐š‚.๐šœ๐šž๐šŒ๐šŒโ‰ฅ1
๐™ฝ๐™พ๐™ณ๐™ด๐š‚.๐šœ๐šž๐šŒ๐šŒโ‰ค|๐™ฝ๐™พ๐™ณ๐™ด๐š‚|
Purpose

All variables associated with the ๐šœ๐šž๐šŒ๐šŒ attribute of the ๐™ฝ๐™พ๐™ณ๐™ด๐š‚ collection should be pairwise distinct. In addition enforce the following condition: if variable ๐™ฝ๐™พ๐™ณ๐™ด๐š‚[i].๐šœ๐šž๐šŒ๐šŒ takes value j then variable ๐™ฝ๐™พ๐™ณ๐™ด๐š‚[j].๐šœ๐šž๐šŒ๐šŒ takes value i. This can be interpreted as a graph-covering problem where one has to cover a digraph G with circuits of length two in such a way that each vertex of G belongs to one single circuit.

Example
๐š’๐š—๐š๐šŽ๐šก-1๐šœ๐šž๐šŒ๐šŒ-3,๐š’๐š—๐š๐šŽ๐šก-2๐šœ๐šž๐šŒ๐šŒ-4,๐š’๐š—๐š๐šŽ๐šก-3๐šœ๐šž๐šŒ๐šŒ-1,๐š’๐š—๐š๐šŽ๐šก-4๐šœ๐šž๐šŒ๐šŒ-2

The ๐šœ๐šข๐š–๐š–๐šŽ๐š๐š›๐š’๐šŒ_๐šŠ๐š•๐š•๐š๐š’๐š๐š๐šŽ๐š›๐šŽ๐š—๐š constraint holds since:

  • ๐™ฝ๐™พ๐™ณ๐™ด๐š‚[1].๐šœ๐šž๐šŒ๐šŒ=3โ‡”๐™ฝ๐™พ๐™ณ๐™ด๐š‚[3].๐šœ๐šž๐šŒ๐šŒ=1,

  • ๐™ฝ๐™พ๐™ณ๐™ด๐š‚[2].๐šœ๐šž๐šŒ๐šŒ=4โ‡”๐™ฝ๐™พ๐™ณ๐™ด๐š‚[4].๐šœ๐šž๐šŒ๐šŒ=2.

Symmetry

Items of ๐™ฝ๐™พ๐™ณ๐™ด๐š‚ are permutable.

Usage

As it was reported inย [Regin99], this constraint is useful to express matches between persons. The ๐šœ๐šข๐š–๐š–๐šŽ๐š๐š›๐š’๐šŒ_๐šŠ๐š•๐š•๐š๐š’๐š๐š๐šŽ๐š›๐šŽ๐š—๐šconstraint also appears implicitly in the cycle cover problem and corresponds to the four conditions given in section 1 Modeling the Cycle Cover Problem ofย [PesantSoriano98].

Remark

This constraint is referenced under the name ๐š˜๐š—๐šŽ_๐š๐šŠ๐šŒ๐š๐š˜๐š› inย [HenzMullerThiel02] as well as inย [Trick02]. From a modelling point of view this constraint can be expressed with the ๐šŒ๐šข๐šŒ๐š•๐šŽ constraintย [BeldiceanuContejean94] where one imposes the additional condition that each cycle has only two nodes.

Algorithm

A filtering algorithm for the ๐šœ๐šข๐š–๐š–๐šŽ๐š๐š›๐š’๐šŒ_๐šŠ๐š•๐š•๐š๐š’๐š๐š๐šŽ๐š›๐šŽ๐š—๐š constraint was proposed by J. -C.ย Rรฉgin inย [Regin99]. It achieves arc-consistency and its running time is dominated by the complexity of finding all edges that do not belong to any maximum cardinality matching in an undirected n-vertex, m-edge graph, i.e.,ย O(mยทn).

Reformulation

The ๐šœ๐šข๐š–๐š–๐šŽ๐š๐š›๐š’๐šŒ_๐šŠ๐š•๐š•๐š๐š’๐š๐š๐šŽ๐š›๐šŽ๐š—๐š(๐™ฝ๐™พ๐™ณ๐™ด๐š‚) constraint can be expressed in term of a conjunction of |๐™ฝ๐™พ๐™ณ๐™ด๐š‚| 2 reified constraints of the form ๐™ฝ๐™พ๐™ณ๐™ด๐š‚[i].๐šœ๐šž๐šŒ๐šŒ=jโ‡”๐™ฝ๐™พ๐™ณ๐™ด๐š‚[j].๐šœ๐šž๐šŒ๐šŒ=i (1โ‰คi,jโ‰ค|๐™ฝ๐™พ๐™ณ๐™ด๐š‚|). The ๐šœ๐šข๐š–๐š–๐šŽ๐š๐š›๐š’๐šŒ_๐šŠ๐š•๐š•๐š๐š’๐š๐š๐šŽ๐š›๐šŽ๐š—๐š constraint can also be reformulated as an ๐š’๐š—๐šŸ๐šŽ๐š›๐šœ๐šŽ constraint as shown below:

๐šœ๐šข๐š–๐š–๐šŽ๐š๐š›๐š’๐šŒ_๐šŠ๐š•๐š•๐š๐š’๐š๐š๐šŽ๐š›๐šŽ๐š—๐š๐š’๐š—๐š๐šŽ๐šก-1๐šœ๐šž๐šŒ๐šŒ-s 1 ,๐š’๐š—๐š๐šŽ๐šก-2๐šœ๐šž๐šŒ๐šŒ-s 2 ,โ‹ฎโ‹ฎ๐š’๐š—๐š๐šŽ๐šก-n๐šœ๐šž๐šŒ๐šŒ-s n
๐š’๐š—๐šŸ๐šŽ๐š›๐šœ๐šŽ๐š’๐š—๐š๐šŽ๐šก-1๐šœ๐šž๐šŒ๐šŒ-s 1 ๐š™๐š›๐šŽ๐š-s 1 ,๐š’๐š—๐š๐šŽ๐šก-2๐šœ๐šž๐šŒ๐šŒ-s 2 ๐š™๐š›๐šŽ๐š-s 2 ,โ‹ฎโ‹ฎโ‹ฎ๐š’๐š—๐š๐šŽ๐šก-n๐šœ๐šž๐šŒ๐šŒ-s n ๐š™๐š›๐šŽ๐š-s n
See also

common keyword: ๐šŠ๐š•๐š•๐š๐š’๐š๐š๐šŽ๐š›๐šŽ๐š—๐š, ๐šŒ๐šข๐šŒ๐š•๐šŽ, ๐š’๐š—๐šŸ๐šŽ๐š›๐šœ๐šŽย (permutation).

related: ๐š›๐š˜๐š˜๐š๐šœ.

Keywords

application area: sport timetabling.

characteristic of a constraint: all different, disequality.

combinatorial object: permutation, matching.

constraint type: graph constraint, timetabling constraint, graph partitioning constraint.

filtering: arc-consistency.

final graph structure: circuit.

modelling: cycle.

Arc input(s)

๐™ฝ๐™พ๐™ณ๐™ด๐š‚

Arc generator
๐ถ๐ฟ๐ผ๐‘„๐‘ˆ๐ธ(โ‰ )โ†ฆ๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐š—๐š˜๐š๐šŽ๐šœ1,๐š—๐š˜๐š๐šŽ๐šœ2)

Arc arity
Arc constraint(s)
โ€ข ๐š—๐š˜๐š๐šŽ๐šœ1.๐šœ๐šž๐šŒ๐šŒ=๐š—๐š˜๐š๐šŽ๐šœ2.๐š’๐š—๐š๐šŽ๐šก
โ€ข ๐š—๐š˜๐š๐šŽ๐šœ2.๐šœ๐šž๐šŒ๐šŒ=๐š—๐š˜๐š๐šŽ๐šœ1.๐š’๐š—๐š๐šŽ๐šก
Graph property(ies)
๐๐€๐‘๐‚=|๐™ฝ๐™พ๐™ณ๐™ด๐š‚|

Graph model

In order to express the binary constraint that links two vertices one has to make explicit the identifier of the vertices.

Partsย (A) andย (B) of Figureย 5.331.1 respectively show the initial and final graph associated with the Example slot. Since we use the ๐๐€๐‘๐‚ graph property, the arcs of the final graph are stressed in bold.

Figure 5.331.1. Initial and final graph of the ๐šœ๐šข๐š–๐š–๐šŽ๐š๐š›๐š’๐šŒ_๐šŠ๐š•๐š•๐š๐š’๐š๐š๐šŽ๐š›๐šŽ๐š—๐š constraint
ctrs/symmetric_alldifferentActrs/symmetric_alldifferentB
(a) (b)
Signature

Since all the ๐š’๐š—๐š๐šŽ๐šก attributes of the ๐™ฝ๐™พ๐™ณ๐™ด๐š‚ collection are distinct, and because of the first condition ๐š—๐š˜๐š๐šŽ๐šœ1.๐šœ๐šž๐šŒ๐šŒ=๐š—๐š˜๐š๐šŽ๐šœ2.๐š’๐š—๐š๐šŽ๐šก of the arc constraint, each vertex of the final graph has at most one successor. Therefore the maximum number of arcs of the final graph is equal to the maximum number of vertices |๐™ฝ๐™พ๐™ณ๐™ด๐š‚| of the final graph. So we can rewrite ๐๐€๐‘๐‚=|๐™ฝ๐™พ๐™ณ๐™ด๐š‚| to ๐๐€๐‘๐‚โ‰ฅ|๐™ฝ๐™พ๐™ณ๐™ด๐š‚| and simplify ๐๐€๐‘๐‚ ยฏ ฬฒ to ๐๐€๐‘๐‚ ยฏ.