[Lauriere78]

$\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}\left(\mathrm{𝙽𝙾𝙳𝙴𝚂}\right)$

$\mathrm{𝚊𝚝𝚘𝚞𝚛}$, $\mathrm{𝚌𝚢𝚌𝚕𝚎}$.

The $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ constraint holds since its $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ argument depicts the following Hamiltonian circuit visiting successively the vertices 1, 2, 3, 4 and 1.

Figure 5.66.1 gives all solutions to the following non ground instance of the $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ constraint: $S_1\in [3,4]$, $S_2\in [1,2]$, $S_3\in [1,4]$, $S_4\in [2,4]$, $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$$\left(\langle 1S_1,2S_2,3S_3,4S_4\rangle \right)$.

Figure 5.66.1. All solutions corresponding to the non ground example of the $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ constraint of the All solutions slot (the $\mathrm{𝚒𝚗𝚍𝚎𝚡}$ attribute is displayed as indices of the $\mathrm{𝚜𝚞𝚌𝚌}$ attribute)

Items of $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ are permutable.

In the original $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ constraint of CHIP the $\mathrm{𝚒𝚗𝚍𝚎𝚡}$ attribute was not explicitly present. It was implicitly defined as the position of a variable in a list.

Within the context of linear programming [AlthausBockmayrElfKasperJungerMehlhorn02] this constraint was introduced under the name $\mathrm{𝚊𝚝𝚘𝚞𝚛}$. In the same context [Hooker07book] provides continuous relaxations of the $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ constraint.

Within the KOALOG constraint system this constraint is called $\mathrm{𝚌𝚢𝚌𝚕𝚎}$.

Since all $\mathrm{𝚜𝚞𝚌𝚌}$ variables of the $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ collection have to take distinct values one can reuse the algorithms associated with the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint. A second necessary condition is to have no more than one strongly connected component. Pruning for enforcing this condition can be done by forcing all strong bridges to belong to the final solution, since otherwise the strongly connected component would be broken apart. A third necessary condition is that, if the graph is bipartite then the number of vertices of each class should be identical. Consequently if the number of vertices is odd (i.e., $\left|\mathrm{𝙽𝙾𝙳𝙴𝚂}\right|$ is odd) the graph should not be bipartite. Further necessary conditions (useful when the graph is sparse) combining the fact that we have a perfect matching and a single strongly connected component can be found in [ShufetBerliner94]. These conditions forget about the orientation of the arcs of the graph and characterise new required elementary chains. A typical pattern involving four vertices is depicted by Figure 5.66.2 where we assume that:

• There is an elementary chain between $c$ and $d$ (depicted by a dashed edge),

• $b$ has exactly 3 neighbours.

In this context the edge between $a$ and $b$ is mandatory in any covering (i.e., the arc from $a$ to $b$ or the arc from $b$ to $a$) since otherwise a small circuit involving $b$, $c$ and $d$ would be created.

Figure 5.66.2. Reasoning about elementary chains and degrees: if we have an elementary chain between $c$ and $d$ and if $b$ has 3 neighbours then the edge $(a,b)$ is mandatory.

When the graph is planar [HopcroftTarjan74][Deo76] one can also use as a necessary condition discovered by Grinberg [Grinberg68] for pruning.

Finally, another approach based an the notion of 1-toughness [Chvatal73] was proposed in [KayaHooker06] and evaluated for small graphs (i.e., graphs with up to 15 vertices).

Let $n$ and $s_1,s_2,\cdots ,s_n$ respectively denotes the number of vertices (i.e., $\left|\mathrm{𝙽𝙾𝙳𝙴𝚂}\right|$) and the successor variables associated with vertices $1,2,\cdots ,n$. The $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ constraint can be reformulated as a conjunction of one $\mathrm{𝚍𝚘𝚖𝚊𝚒𝚗}$ constraint, two $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints, and $n$ $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraints.

• First, we state an $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$(\langle s_1,$ $s_2,\cdots ,s_n\rangle )$ constraint for enforcing distinct values to be assigned to the successor variables.

• Second, the key idea is, starting from vertex 1, to successively extract the vertices $t_1,t_2,...,t_{n-1}$ of the circuit until we come back on vertex 1, where $t_i$ (with $i\in [2,n-1]$) denotes the successor of $t_{i-1}$ and $t_1$ the successor of vertex 1. Since we have one single circuit all the $t_1,t_2,...,t_{n-1}$ should be different from 1. Consequently we state a $\mathrm{𝚍𝚘𝚖𝚊𝚒𝚗}$$(\langle t_1,t_2,...,t_{n_1}\rangle ,2,n)$ constraint for declaring their initial domains. To express the link between consecutive $t_i$ we also state a conjunction of $n$ $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraints of the form:

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(1,\langle s_1,s_2,\cdots ,s_n\rangle ,t_1)$,

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(t_1,\langle s_1,s_2,\cdots ,s_n\rangle ,t_2)$,

   $\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots$

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(t_{n-1},\langle s_1,s_2,\cdots ,s_n\rangle ,1)$.

• Finally we add a redundant constraint for stating that all $t_i$ (with $i\in [1,n-1]$) are distinct, i.e. $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$\left(\langle t_1,t_2,\cdots ,t_{n-1}\rangle \right)$.

Number of solutions for $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$: domains $0..n$

circuit in Gecode, circuit in JaCoP, circuit in SICStus.

common keyword: $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ (permutation), $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}\_\mathrm{𝚌𝚕𝚞𝚜𝚝𝚎𝚛}$ (graph constraint, one_succ), $\mathrm{𝚙𝚊𝚝𝚑}$ (graph partitioning constraint, one_succ), $\mathrm{𝚙𝚛𝚘𝚙𝚎𝚛}\_\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ (permutation, one_succ), $\mathrm{𝚝𝚘𝚞𝚛}$ (graph partitioning constraint, Hamiltonian).

generalisation: $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ (introduce a variable for the number of circuits).

implies: $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$, $\mathrm{𝚙𝚛𝚘𝚙𝚎𝚛}\_\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$, $\mathrm{𝚝𝚠𝚒𝚗}$.

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

related: $\mathrm{𝚜𝚝𝚛𝚘𝚗𝚐𝚕𝚢}\_\mathrm{𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍}$.

combinatorial object: permutation.

constraint type: graph constraint, graph partitioning constraint.

filtering: linear programming, planarity test, strong bridge, DFS-bottleneck.

final graph structure: circuit, one_succ.

problems: Hamiltonian.