Hamiltonian Circuit (cross92)

Run LPL Code  ,  PDF Document

Problem

This problem is another example for tour finding in a graph (see icosian). Given a graph as in Figure ?? find a tour in the graph, if it exists.

Modeling Steps

1. This problem can be formulated as a TSP problem, where the vertex set is i,j ∈{1,…, 92}. The edge lengths d_i,j are calculate by

   

   Replace all edge length ≥ 3.1 with 99′999.

   (Another way to specify the edge length is as follows: set all edge lengths to 0 if d_i,j ≤ 3.1 else set them to 1.)

2. Apply now the same model as in icosian.

model cross92 "Hamiltonian Circuit"; 
    set i,j  "set of vertices of a graph"; 
    parameter d{i,j} "distance between i and j"; 
    binary variable x{i,j|i<>j}; 
    constraint 
      A{i}: sum{j} x = 1; 
      B{j}: sum{i} x = 1; 
      F{i,j|j>i}: x[i,j] + x[j,i] <= 1; 
    minimize obj: sum{i,j} d*x; 
    Write('minimal tour is: %5.2f' n', obj); 
    draw; 
    model data,D "The star"; 
      i:=1..92; 
      set k:=1..#i/4; 
      parameter 
        x{k}:=[ 0 -1 -1 -2 -3 -4 -4 -4 -2 -1 -1 -1 -2 -4 -5 -5 -5 -6 -7 -7 -8 -9 -10]; 
        y{k}:=[10 10  8  7  7  7  6  5  5  4  3  2  1  1  2  3  4  4  4  2  1  1   1]; 
        X{i}:=(if(i<=23,x[i],  i<=46,-y[i-23], 
                i<=69,-x[i-46],  y[i-69]) 
              +10)/3*2 +.3; 
        Y{i}:=(if(i<=23,y[i],i<=46, x[i-23], 
                i<=69,-y[i-46], -x[i-69]) 
              +10)/3*2 +.3;; 
      d{i,j}:= Sqrt((X[j]-X[i])^2+(Y[j]-Y[i])^2); 
      d{i,j|d>=3.1}:=99999; 
    end 
    model draw; 
      Draw.Scale(40,40); 
      Draw.DefFont('Verdana',10); 
      {i,j|d<3.1} Draw.Line(D.X[i],D.Y[i],D.X[j],D.Y[j],2); 
      {i,j|x}  Draw.Line(D.X[i],D.Y[i],D.X[j],D.Y[j],3,3); 
      {i}  Draw.Circle(i&'',D.X,D.Y,.2,1,0); 
   end 
  end

Solution

The solution of this game is shown in Figure 1. Since there is no edge with length of 99′999 in the tour, a tour in the cross92-graph exists.

---

---

References