Global Constraint Catalog: Csymmetric_alldifferent

5.397. symmetric_alldifferent_loop

DESCRIPTION

LINKS

GRAPH

Origin

Derived from $𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$

Constraint

$𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚕𝚘𝚘𝚙 (𝙽𝙾𝙳𝙴𝚂)$

Synonyms

$𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚊𝚕𝚕𝚍𝚒𝚏𝚏_𝚕𝚘𝚘𝚙$ , $𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚊𝚕𝚕𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝_𝚕𝚘𝚘𝚙$ , $𝚜𝚢𝚖𝚖_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚕𝚘𝚘𝚙$ , $𝚜𝚢𝚖𝚖_𝚊𝚕𝚕𝚍𝚒𝚏𝚏_𝚕𝚘𝚘𝚙$ , $𝚜𝚢𝚖𝚖_𝚊𝚕𝚕𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝_𝚕𝚘𝚘𝚙$ .

Argument

𝙽𝙾𝙳𝙴𝚂

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚗𝚍𝚎𝚡 - 𝚒𝚗𝚝, 𝚜𝚞𝚌𝚌 - 𝚍𝚟𝚊𝚛)

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙽𝙾𝙳𝙴𝚂, [𝚒𝚗𝚍𝚎𝚡, 𝚜𝚞𝚌𝚌])

𝙽𝙾𝙳𝙴𝚂 . 𝚒𝚗𝚍𝚎𝚡 \geq 1

𝙽𝙾𝙳𝙴𝚂 . 𝚒𝚗𝚍𝚎𝚡 \leq | 𝙽𝙾𝙳𝙴𝚂 |

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

(𝙽𝙾𝙳𝙴𝚂, 𝚒𝚗𝚍𝚎𝚡)

𝙽𝙾𝙳𝙴𝚂 . 𝚜𝚞𝚌𝚌 \geq 1

𝙽𝙾𝙳𝙴𝚂 . 𝚜𝚞𝚌𝚌 \leq | 𝙽𝙾𝙳𝙴𝚂 |

Purpose

All variables associated with the $𝚜𝚞𝚌𝚌$ attribute of the $𝙽𝙾𝙳𝙴𝚂$ collection should be pairwise distinct. In addition enforce the following condition: if variable $𝙽𝙾𝙳𝙴𝚂 [i] . 𝚜𝚞𝚌𝚌$ is assigned value $j$ then variable $𝙽𝙾𝙳𝙴𝚂 [j] . 𝚜𝚞𝚌𝚌$ is assigned value $i$ . Note that $i$ and $j$ are not necessarily distinct. This can be interpreted as a graph-covering problem where one has to cover a digraph $G$ with circuits of length two or one in such a way that each vertex of $G$ belongs to a single circuit.

Example

(\begin{matrix} 〈\begin{matrix} 𝚒𝚗𝚍𝚎𝚡 - 1 & 𝚜𝚞𝚌𝚌 - 1, \\ 𝚒𝚗𝚍𝚎𝚡 - 2 & 𝚜𝚞𝚌𝚌 - 4, \\ 𝚒𝚗𝚍𝚎𝚡 - 3 & 𝚜𝚞𝚌𝚌 - 3, \\ 𝚒𝚗𝚍𝚎𝚡 - 4 & 𝚜𝚞𝚌𝚌 - 2 \end{matrix}〉 \end{matrix})

The $𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚕𝚘𝚘𝚙$ constraint holds since:

We have two loops respectively corresponding to $𝙽𝙾𝙳𝙴𝚂 [1] . 𝚜𝚞𝚌𝚌 = 1$ and $𝙽𝙾𝙳𝙴𝚂 [3] . 𝚜𝚞𝚌𝚌 = 3$ .
We have one circuit of length 2 corresponding to $𝙽𝙾𝙳𝙴𝚂 [2] . 𝚜𝚞𝚌𝚌 = 4 \Leftrightarrow 𝙽𝙾𝙳𝙴𝚂 [4] . 𝚜𝚞𝚌𝚌 = 2$ .

Figure 5.397.1 provides a second example involving a $𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚕𝚘𝚘𝚙$ constraint.

Figure 5.397.1. (A) Magic square Duerer where cells that belong to a same cycle are coloured identically by a colour different from grey; each cell has an index in its upper left corner (in red) and a value (in blue). (B) Corresponding graph where there is an arc from node $i$ to node $j$ if and only if the value of cell $i$ is equal to the index of cell $j$ . (C) Collection of nodes passed to the $𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚕𝚘𝚘𝚙$ constraint: the four self-loops of the graph correspond to the four grey cells of the magic square such that the value of the cell (in blue) is equal to the index of the cell (in red).

All solutions

Figure 5.397.2 gives all solutions to the following non ground instance of the $𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚕𝚘𝚘𝚙$ constraint: $S_{1} \in [2, 5]$ , $S_{2} \in [1, 3]$ , $S_{3} \in [1, 4]$ , $S_{4} \in [2, 4]$ , $S_{5} \in [1, 5]$ , $𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚕𝚘𝚘𝚙$ $(〈 1 S_{1}, 2 S_{2}, 3 S_{3}, 4 S_{4}, 5 S_{5} 〉)$ .

Figure 5.397.2. 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 and self loops are coloured in red.

Typical

| 𝙽𝙾𝙳𝙴𝚂 | \geq 4

Symmetry

Items of $𝙽𝙾𝙳𝙴𝚂$ are permutable.

Algorithm

An arc-consistency filtering algorithm for the $𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚕𝚘𝚘𝚙$ constraint is described in [Cymer13], [CymerPhD13]. The algorithm is based on the following ideas:

First, one can map solutions of the $𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚕𝚘𝚘𝚙$ 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 a self-loop, 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 any perfect $(g, f)$ -matchings, and therefore prune the corresponding variables.

Counting

Length ( $n$ )	2	3	4	5	6	7	8	9	10
Solutions	2	4	10	26	76	232	764	2620	9496

Number of solutions for $𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚕𝚘𝚘𝚙$ : domains $0 . . n$

ctrs/symmetric_alldifferent_loop-3-tikz

ctrs/symmetric_alldifferent_loop-4-tikz

implies: $𝚝𝚠𝚒𝚗$ .

implies (items to collection): $𝚕𝚎𝚡_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ .

Keywords

characteristic of a constraint: all different, disequality.

combinatorial object: permutation, involution, matching.

constraint type: graph constraint, graph partitioning constraint.

final graph structure: circuit.

modelling: cycle.

Cond. implications

$𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚕𝚘𝚘𝚙 (𝙽𝙾𝙳𝙴𝚂)$

implies $𝚙𝚎𝚛𝚖𝚞𝚝𝚊𝚝𝚒𝚘𝚗$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 : 𝙽𝙾𝙳𝙴𝚂)$ .

Arc input(s)

$𝙽𝙾𝙳𝙴𝚂$

Arc generator

𝐶𝐿𝐼𝑄𝑈𝐸

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚗𝚘𝚍𝚎𝚜 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.397.3 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.397.3. Initial and final graph of the $𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚕𝚘𝚘𝚙$ constraint


(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 $𝐍𝐀𝐑𝐂 \geq | 𝙽𝙾𝙳𝙴𝚂 |$ and simplify $\underset{̲}{\bar{𝐍𝐀𝐑𝐂}}$ to $\bar{𝐍𝐀𝐑𝐂}$ .

Global Constraint Catalog

5. Global Constraint Catalogue

5.397. symmetric_alldifferent_loop

Figure 5.397.3. Initial and final graph of the 𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚕𝚘𝚘𝚙 constraint

Figure 5.397.3. Initial and final graph of the $𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚕𝚘𝚘𝚙$ constraint