5.396. symmetric_alldifferent_except_0

DESCRIPTIONLINKS
Origin

Derived from πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš

Constraint

πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0(π™½π™Ύπ™³π™΄πš‚)

Synonyms

πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŠπš•πš•πšπš’πšπš_πšŽπš‘πšŒπšŽπš™πš_0, πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŠπš•πš•πšπš’πšœπšπš’πš—πšŒπš_πšŽπš‘πšŒπšŽπš™πš_0, πšœπš’πš–πš–_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0, πšœπš’πš–πš–_πšŠπš•πš•πšπš’πšπš_πšŽπš‘πšŒπšŽπš™πš_0, πšœπš’πš–πš–_πšŠπš•πš•πšπš’πšœπšπš’πš—πšŒπš_πšŽπš‘πšŒπšŽπš™πš_0.

Argument
π™½π™Ύπ™³π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,𝚜𝚞𝚌𝚌-πšπšŸπšŠπš›)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(π™½π™Ύπ™³π™΄πš‚,[πš’πš—πšπšŽπš‘,𝚜𝚞𝚌𝚌])
π™½π™Ύπ™³π™΄πš‚.πš’πš—πšπšŽπš‘β‰₯1
π™½π™Ύπ™³π™΄πš‚.πš’πš—πšπšŽπš‘β‰€|π™½π™Ύπ™³π™΄πš‚|
πšπš’πšœπšπš’πš—πšŒπš(π™½π™Ύπ™³π™΄πš‚,πš’πš—πšπšŽπš‘)
π™½π™Ύπ™³π™΄πš‚.𝚜𝚞𝚌𝚌β‰₯0
π™½π™Ύπ™³π™΄πš‚.πšœπšžπšŒπšŒβ‰€|π™½π™Ύπ™³π™΄πš‚|
Purpose

Enforce the following three conditions:

  1. βˆ€i∈[1,|π™½π™Ύπ™³π™΄πš‚|], βˆ€j∈[1,|π™½π™Ύπ™³π™΄πš‚|], (jβ‰ i): π™½π™Ύπ™³π™΄πš‚[i].𝚜𝚞𝚌𝚌=0βˆ¨π™½π™Ύπ™³π™΄πš‚[j].𝚜𝚞𝚌𝚌=0βˆ¨π™½π™Ύπ™³π™΄πš‚[i].πšœπšžπšŒπšŒβ‰ π™½π™Ύπ™³π™΄πš‚[j].𝚜𝚞𝚌𝚌.

  2. βˆ€i∈[1,|π™½π™Ύπ™³π™΄πš‚|]:π™½π™Ύπ™³π™΄πš‚[i].πšœπšžπšŒπšŒβ‰ i.

  3. π™½π™Ύπ™³π™΄πš‚[i].𝚜𝚞𝚌𝚌=j∧jβ‰ i∧jβ‰ 0β‡”π™½π™Ύπ™³π™΄πš‚[j].𝚜𝚞𝚌𝚌=i∧iβ‰ j∧iβ‰ 0.

Example
πš’πš—πšπšŽπš‘-1𝚜𝚞𝚌𝚌-3,πš’πš—πšπšŽπš‘-2𝚜𝚞𝚌𝚌-0,πš’πš—πšπšŽπš‘-3𝚜𝚞𝚌𝚌-1,πš’πš—πšπšŽπš‘-4𝚜𝚞𝚌𝚌-0

The πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0 constraint holds since:

  • π™½π™Ύπ™³π™΄πš‚[1].𝚜𝚞𝚌𝚌=3β‡”π™½π™Ύπ™³π™΄πš‚[3].𝚜𝚞𝚌𝚌=1,

  • π™½π™Ύπ™³π™΄πš‚[2].𝚜𝚞𝚌𝚌=0 and value 2 is not assigned to any variable.

  • π™½π™Ύπ™³π™΄πš‚[4].𝚜𝚞𝚌𝚌=0 and value 4 is not assigned to any variable.

Given 3 successor variables that have to be assigned a value in interval [0,3], the solutions to the πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0 (βŒ©πš’πš—πšπšŽπš‘-1 𝚜𝚞𝚌𝚌-s 1 ,πš’πš—πšπšŽπš‘-2 𝚜𝚞𝚌𝚌-s 2 ,πš’πš—πšπšŽπš‘-3 𝚜𝚞𝚌𝚌-s 3 βŒͺ) constraint are 〈1 0,2 0,3 0βŒͺ, 〈1 0,2 3,3 2βŒͺ, 〈1 2,2 1,3 0βŒͺ, and 〈1 3,2 0,3 1βŒͺ.

Given 4 successor variables that have to be assigned a value in interval [0,3], the solutions to the πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0 (βŒ©πš’πš—πšπšŽπš‘-1 𝚜𝚞𝚌𝚌-s 1 ,πš’πš—πšπšŽπš‘-2 𝚜𝚞𝚌𝚌-s 2 ,πš’πš—πšπšŽπš‘-3 𝚜𝚞𝚌𝚌-s 3 ,πš’πš—πšπšŽπš‘-4 𝚜𝚞𝚌𝚌-s 4 βŒͺ) constraint are 〈1 0,2 0,3 0,4 0βŒͺ, 〈1 0,2 0,3 4,4 3βŒͺ, 〈1 0,2 3,3 2,4 0βŒͺ, 〈1 0,2 4,3 0,4 2βŒͺ, 〈1 2,2 1,3 0,4 0βŒͺ, 〈1 2,2 1,3 4,4 3βŒͺ, 〈1 3,2 0,3 1,4 0βŒͺ, 〈1 3,2 4,3 1,4 2βŒͺ, 〈1 4,2 0,3 0,4 1βŒͺ, 〈1 4,2 3,3 2,4 1βŒͺ.

All solutions

FigureΒ 5.396.1 gives all solutions to the following non ground instance of the πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0 constraint: S 1 ∈[0..5], S 2 ∈[1..3], S 3 ∈[1..4], S 4 ∈[0..3], S 5 ∈[0..2], πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0(〈1 S 1 ,2 S 2 ,3 S 3 ,4 S 4 ,5 S 5 βŒͺ).

Figure 5.396.1. All solutions corresponding to the non ground example of the πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0 constraint of the All solutions slot (the πš’πš—πšπšŽπš‘ attribute is displayed as indices of the 𝚜𝚞𝚌𝚌 attribute)
ctrs/symmetric_alldifferent_except_0-1-tikz
Typical
|π™½π™Ύπ™³π™΄πš‚|β‰₯4
πš–πš’πš—πšŸπšŠπš•(π™½π™Ύπ™³π™΄πš‚.𝚜𝚞𝚌𝚌)=0
πš–πšŠπš‘πšŸπšŠπš•(π™½π™Ύπ™³π™΄πš‚.𝚜𝚞𝚌𝚌)>0
Symmetry

Items of π™½π™Ύπ™³π™΄πš‚ are permutable.

Usage

Within the context of sport scheduling, π™½π™Ύπ™³π™΄πš‚[i].𝚜𝚞𝚌𝚌=j (iβ‰ 0,jβ‰ 0,iβ‰ j) is interpreted as the fact that team i plays against team j, while π™½π™Ύπ™³π™΄πš‚[i].𝚜𝚞𝚌𝚌=0 (iβ‰ 0) is interpreted as the fact that team i does not play at all.

Algorithm

An arc-consistency filtering algorithm for the πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0 constraint is described inΒ [Cymer13], [CymerPhD13]. The algorithm is based on the following facts:

  • First, one can map solutions to the πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0 constraint to perfect (g,f)-matchings in a non-bipartite graph derived from the domain of the variables of the constraint where g(x)=0, f(x)=1 for vertices x which have 0 in their domain, and g(x)=f(x)=1 for all the remaining vertices. A perfect (g,f)-matching β„³ of a graph is a subset of edges such that every vertex x is incident with the number of edges in β„³ between g(x) and f(x).

  • Second, Gallai-Edmonds decompositionΒ [Gallai63], [Edmonds65] allows to find out all edges that do not belong to any perfect (g,f)-matchings, and therefore prune the corresponding variables.

Counting
Length (n)2345678
Solutions24102676232764

Number of solutions for πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0: domains 0..n

ctrs/symmetric_alldifferent_except_0-2-tikz

ctrs/symmetric_alldifferent_except_0-3-tikz

See also

implied by: πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

implies (items to collection): πš”_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, πš•πšŽπš‘_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

Keywords

application area: sport timetabling.

characteristic of a constraint: joker value.

combinatorial object: matching.

constraint type: predefined constraint, timetabling constraint.

Cond. implications

πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0(π™½π™Ύπ™³π™΄πš‚)

Β Β implies πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚:π™½π™Ύπ™³π™΄πš‚).