5.53. circuit

DESCRIPTIONLINKSGRAPH
Origin

[Lauriere78]

Constraint

πšŒπš’πš›πšŒπšžπš’πš(π™½π™Ύπ™³π™΄πš‚)

Synonyms

πšŠπšπš˜πšžπš›, πšŒπš’πšŒπš•πšŽ.

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

Enforce to cover a digraph G described by the π™½π™Ύπ™³π™΄πš‚ collection with one circuit visiting once all vertices of G.

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

The πšŒπš’πš›πšŒπšžπš’πš constraint holds since its π™½π™Ύπ™³π™΄πš‚ argument depicts the following Hamiltonian circuit visiting successively the vertices 1, 2, 3, 4 and 1.

Typical
|π™½π™Ύπ™³π™΄πš‚|>2
Symmetry

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

Remark

In the original πšŒπš’πš›πšŒπšžπš’πš constraint of CHIP the πš’πš—πšπšŽπš‘ 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 πšŠπšπš˜πšžπš›. In the same contextΒ [Hooker07book] provides continuous relaxations of the πšŒπš’πš›πšŒπšžπš’πš constraint.

Within the KOALOG constraint system this constraint is called πšŒπš’πšŒπš•πšŽ.

Algorithm

Since all 𝚜𝚞𝚌𝚌 variables of the π™½π™Ύπ™³π™΄πš‚ collection have to take distinct values one can reuse the algorithms associated with the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš 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. When the number of vertices is odd (i.e.,Β |π™½π™Ύπ™³π™΄πš‚| is odd) a third necessary condition is to have a bipartite graph (see the Algorithm slot of the πš‹πš’πš™πšŠπš›πšπš’πšπšŽ constraint).

Further necessary conditions (useful when the graph is sparse) combining the fact that we have a perfect matching and one 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.53.1 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.53.1. 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.
ctrs/circuit1

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).

Systems

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

See also

common keyword: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (permutation), πšŒπš’πš›πšŒπšžπš’πš_πšŒπš•πšžπšœπšπšŽπš›Β (graph constraint, one_succ), πš™πšŠπšπš‘Β (graph partitioning constraint, one_succ), πšπš˜πšžπš›Β (graph partitioning constraint, Hamiltonian).

generalisation: πšŒπš’πšŒπš•πšŽΒ (introduce a variable for the number of circuits).

implies: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

related: πšœπšπš›πš˜πš—πšπš•πš’_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš.

Keywords

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.

Arc input(s)

π™½π™Ύπ™³π™΄πš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš—πš˜πšπšŽπšœ1,πš—πš˜πšπšŽπšœ2)

Arc arity
Arc constraint(s)
πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌=πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘
Graph property(ies)
β€’ 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂=|π™½π™Ύπ™³π™΄πš‚|
β€’ πŒπ€π—_πˆπƒ=1

Graph class
𝙾𝙽𝙴_πš‚πš„π™²π™²

Graph model

The first graph property enforces to have one single strongly connected component containing |π™½π™Ύπ™³π™΄πš‚| vertices. The second graph property imposes to only have circuits. Since each vertex of the final graph has only one successor we do not need to use set variables for representing the successors of a vertex.

PartsΒ (A) andΒ (B) of FigureΒ 5.53.2 respectively show the initial and final graph associated with the Example slot. The πšŒπš’πš›πšŒπšžπš’πš constraint holds since the final graph consists of one circuit mentioning once every vertex of the initial graph.

Figure 5.53.2. Initial and final graph of the πšŒπš’πš›πšŒπšžπš’πš constraint
ctrs/circuitActrs/circuitB
(a) (b)
Signature

Since the initial graph contains |π™½π™Ύπ™³π™΄πš‚| vertices the final graph contains at most |π™½π™Ύπ™³π™΄πš‚| vertices. Therefore we can rewrite the graph property 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂=|π™½π™Ύπ™³π™΄πš‚| to 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂β‰₯|π™½π™Ύπ™³π™΄πš‚|. This leads to simplify 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 Β― Μ² to 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 Β―.

Because of the graph property 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂=|π™½π™Ύπ™³π™΄πš‚| the final graph contains at least one vertex. Since a vertex v belongs to the final graph only if there is an arc that has v as one of its extremities the final graph contains at least one arc. Therefore πŒπ€π—_πˆπƒ is greater than or equal to 1. So we can rewrite the graph property πŒπ€π—_πˆπƒ=1 to πŒπ€π—_πˆπƒβ‰€1. This leads to simplify πŒπ€π—_πˆπƒ Β― Μ² to πŒπ€π—_πˆπƒ Μ².