5.396. symmetric_alldifferent_except_0
DESCRIPTION | LINKS |
- Origin
- Constraint
- Synonyms
, , , , .
- Argument
- Restrictions
- Purpose
Enforce the following three conditions:
, , (): .
.
.
- Example
-
The constraint holds since:
,
and value 2 is not assigned to any variable.
and value 4 is not assigned to any variable.
Given 3 successor variables that have to be assigned a value in interval , the solutions to the constraint are , , , and .
Given 4 successor variables that have to be assigned a value in interval , the solutions to the constraint are , , , , , , , , , .
- All solutions
FigureΒ 5.396.1 gives all solutions to the following non ground instance of the constraint: , , , , , .
Figure 5.396.1. All solutions corresponding to the non ground example of the constraint of the All solutions slot (the attribute is displayed as indices of the attribute)
- Typical
- Symmetry
Items of are permutable.
- Usage
Within the context of sport scheduling, () is interpreted as the fact that team plays against team , while () is interpreted as the fact that team does not play at all.
- Algorithm
An arc-consistency filtering algorithm for the constraint is described inΒ [Cymer13], [CymerPhD13]. The algorithm is based on the following facts:
First, one can map solutions to the constraint to perfect -matchings in a non-bipartite graph derived from the domain of the variables of the constraint where , for vertices which have 0 in their domain, and for all the remaining vertices. A perfect -matching of a graph is a subset of edges such that every vertex is incident with the number of edges in between and .
Second, Gallai-Edmonds decompositionΒ [Gallai63], [Edmonds65] allows to find out all edges that do not belong to any perfect -matchings, and therefore prune the corresponding variables.
- Counting
-
Length () 2 3 4 5 6 7 8 Solutions 2 4 10 26 76 232 764 Number of solutions for : domains
- See also
- Keywords
application area: sport timetabling.
characteristic of a constraint: joker value.
combinatorial object: matching.
constraint type: predefined constraint, timetabling constraint.
- Cond. implications