5.335. tour

DESCRIPTIONLINKSGRAPH
Origin

[AlthausBockmayrElfKasperJungerMehlhorn02]

Constraint

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

Synonyms

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

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

Enforce to cover an undirected graph G described by the π™½π™Ύπ™³π™΄πš‚ collection with a Hamiltonian cycle.

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

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

Symmetry

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

Algorithm

When the number of vertices is odd (i.e.,Β |π™½π™Ύπ™³π™΄πš‚| is odd) a necessary condition is to have a bipartite graph (see the Algorithm slot of the πš‹πš’πš™πšŠπš›πšπš’πšπšŽ constraint).

See also

common keyword: πšŒπš’πš›πšŒπšžπš’πšΒ (graph partitioning constraint,Hamiltonian), πšŒπš’πšŒπš•πšŽΒ (graph constraint), πš•πš’πš—πš”_𝚜𝚎𝚝_𝚝𝚘_πš‹πš˜πš˜πš•πšŽπšŠπš—πšœΒ (constraint involving set variables).

used in graph description: πš’πš—_𝚜𝚎𝚝.

Keywords

characteristic of a constraint: undirected graph.

constraint arguments: constraint involving set variables.

constraint type: graph constraint.

filtering: linear programming.

problems: Hamiltonian.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πš’πš—_𝚜𝚎𝚝(πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘,πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌)β‡”πš’πš—_𝚜𝚎𝚝(πš—πš˜πšπšŽπšœ1.πš’πš—πšπšŽπš‘,πš—πš˜πšπšŽπšœ2.𝚜𝚞𝚌𝚌)
Graph property(ies)
𝐍𝐀𝐑𝐂=|π™½π™Ύπ™³π™΄πš‚|*|π™½π™Ύπ™³π™΄πš‚|-|π™½π™Ύπ™³π™΄πš‚|

Arc input(s)

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

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

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

Graph model

The first graph property enforces the subsequent condition: If we have an arc from the i th vertex to the j th vertex then we have also an arc from the j th vertex to the i th vertex. The second graph property enforces the following constraints:

  • We have one strongly connected component containing |π™½π™Ύπ™³π™΄πš‚| vertices,

  • Each vertex has exactly two predecessors and two successors.

PartΒ (A) of FigureΒ 5.335.1 shows the initial graph from which we start. It is derived from the set associated with each vertex. Each set describes the potential values of the 𝚜𝚞𝚌𝚌 attribute of a given vertex. PartΒ (B) of FigureΒ 5.335.1 gives the final graph associated with the Example slot. The πšπš˜πšžπš› constraint holds since the final graph corresponds to a Hamiltonian cycle.

Figure 5.335.1. Initial and final graph of the πšπš˜πšžπš› set constraint
ctrs/tourActrs/tourB
(a) (b)
Signature

Since the maximum number of vertices of the final graph is equal to |π™½π™Ύπ™³π™΄πš‚|, we can rewrite the graph property 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂=|π™½π™Ύπ™³π™΄πš‚| to 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂β‰₯|π™½π™Ύπ™³π™΄πš‚| and simplify 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 Β― Μ² to 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 Β―.