How to use this notebook

This notebook is meant to solve TSP instances by using polyhedral combinatorics techniques.
First  the LP relaxation of the instance  is solved (i.e. A x = 2,  0 <= x <= 1).
The solution is displayed and the user has to provide the necessary cuts, which can be either subtour inequalities or comb inequalities. The subtour inequalities can be found either automatically (by a random min cut algorithm)  or manually. The comb inequalities must be identified manually. The process has to be repeated until an integer solution is found or no evident cuts are available. In the latter case branching is required and user has to go to the appropriate section.

To use the noteook one has first to run the section Routines. Instances are input  in  the section Data.
There are several ways to input instances: these are described within the section. 
The computation is carried out in the section Computation. Detailed instructions are found within the section.
Branching is carried out in the section Branching. Detailed instructions are found within the section.
The section Drawings contain drawings of partial computations of some instances.

Routines

Off[General::spell1]

cutprob[arcs_,prob_]:=Block[{p,r,kk,lt,ki,kj,ri,rj,nn,sets,cutarcs,newarcs,
newprob,minindex,maxindex,mincard,maxcard},
root[k_]:=Block[{kp},kp=k;While[kp!=p[[kp]],kp=p[[kp]]];kp];
nn=Max[arcs];
newarcs=arcs;
newprob=prob;
p=Table[i,{i,nn}];
r=Table[1,{nn}];
For[ lt=0,
    (lt<nn-2) && newarcs != {} ,Null
     ,
    kk=randomelement[newprob];
    ki=newarcs[[kk,1]];
    kj=newarcs[[kk,2]];
    ri=root[ki];
    rj=root[kj];
    If[ri!=rj,
       Which[r[[ri]]>r[[rj]]
            ,p[[rj]]=ri
            ,r[[rj]]>r[[ri]]
            ,p[[ri]]=rj
            ,r[[ri]]==r[[rj]]
            ,p[[rj]]=ri;
             r[[ri]]++
             ];
        lt++;
       ];
    newarcs=Drop[newarcs,{kk}];
    newprob=Drop[newprob,{kk}];
    If[newprob!={},newprob=newprob/Apply[Plus,newprob]];
     ];
   sets=Table[{},{nn}];
   Do[pp=ii;
      While[!p[[pp]]==pp,pp=p[[pp]]];
            AppendTo[sets[[pp]],ii]
                ,{ii,nn}]
     ;
  mincard=nn;maxcard=0;
  Do[If[sets[[ii]] != {},
       If[Length[sets[[ii]]] < mincard, mincard=Length[sets[[ii]]];minindex=ii];
       If[Length[sets[[ii]]]>=maxcard,maxcard=Length[sets[[ii]]];maxindex=ii]],
       {ii,nn}] ;
  Do[If[ii!=minindex && Length[sets[[ii]]] > 0, p[[ii]]=maxindex]
     ,{ii,nn}];
  cutarcs={};
  sets=Table[{},{nn}];
   Do[pp=ii;
      While[!p[[pp]]==pp,pp=p[[pp]]];
            AppendTo[sets[[pp]],ii]
                ,{ii,nn}]
     ;
  Do[ki=arcs[[ii,1]];
     kj=arcs[[ii,2]];
     ri=root[ki];
     rj=root[kj];
     If[ri!=rj,AppendTo[cutarcs,ii]]
     ,{ii,Length[arcs]}];
  {Select[sets, #!={} &],cutarcs}
]

binsearch[a_, v_] := 
      Module[
{n = Length[v], gap, n1, n2, 
          m}, 
gap = n - 1; 
n1 = 1; 
        n2 = n; 
While[
          gap > 1, 
  m = 
            Floor[(n1 + n2)/2]; 
If[
            a  ≥  v[[m]], 
    n1 = 
              m, n2 = m]; 
gap = n2 - n1]; 
        n1
]

randomelement[a_] := 
      Module[{r}, 
r = 
          Random[]; 
binsearch[r, 
          FoldList[Plus, 0, a]]
]

\(cutsearch[posarcs_] := 
      Module[
{posarcvalues, violationfound, maxcounter, 
          set1, set2, cutset, 
          cutvalue}, 
posarcvalues = \(Transpose[
              posarcs]\)[\([1]\)]; 
violationfound = 
          False; 
maxcounter = 
          100; 
While[\(! violationfound\)\  && \ 
            maxcounter > 0, 
\ \ \ \ \ \ \ {{set1, set2}, 
              cutset} = 
            cutprob[\(Transpose[posarcs]\)[\([2]\)], 
              posarcvalues/
                Apply[Plus, 
                  posarcvalues]]; 
\ \ \ \ \ \ \ \ cutvalue = \ \ \ Apply[Plus, 
              posarcvalues[\([cutset]\)]]; 
\ \ \ \ \ \ \ \ violationfound = \((cutvalue\  < \ 
                2 - tolerance)\); 
\ \ \ \ \ \ \ \ \(maxcounter--\)
]; 
If[
          violationfound, 
\ \ \ \ \ \ \ \ \ \ \ nodeset = 
            If[Length[set1] < Length[set2], set1, 
              set2]; 
\ \ \ \ \ \ \ \ \ \ Print["nodeset=", nodeset, "   cutvalue=", 
            cutvalue]
\ \ \ \ \ \ \ \ , 
\ \ \ \ \ Print["not found  subtour violations "]]
]\)

catchcycles := 
      Module[{tourlist, allnodes, cycles, 
          firstnode, 
nextnode, prevnode, auxnode, 
          tournodes}, 
tourlist = 
          Table[{}, {nn}]; 
Do[
          AppendTo[tourlist[[tour[[i, 1]]]], 
            tour[[i, 2]]]; 
    AppendTo[
            tourlist[[tour[[i, 2]]]], tour[[i, 1]]];  , {i, 
            Length[tour]}]; 
allnodes = 
          Range[nn]; 
cycles = {}; 
While[
          allnodes ≠ {}, 
firstnode = 
            allnodes[[1]]; 
tournodes = {firstnode}; 
nextnode = 
            tourlist[[firstnode, 1]]; 
prevnode = 
            firstnode; 
While[
            nextnode ≠  
              firstnode, 
           AppendTo[
              tournodes, 
              nextnode]; 
            auxnode = Complement[
                  tourlist[[nextnode]], {prevnode}][[1]]; 
            prevnode = 
              nextnode; 
            nextnode = 
              auxnode;
              ]; 
AppendTo[cycles, tournodes]; 
allnodes = 
            Complement[allnodes, 
              tournodes]
]; 
  cycles]

takeheurtour[node_] := 
      Module[
{marked, currnode, minvalue, nextnode, tour, 
          tourlength, val}, 
marked = 
          Table[False, {nn}]; 
currnode = 
          node; 
tour = {currnode}; 
tourlength = 0; 
Do[
          marked[[currnode]] = True; 
          minvalue = Infinity; 
  Do[ 
            val = costs[[currnode + 1, 
                  i + 1]] ; 
     If[! marked[[i]]  &&  (val <  
                    minvalue)
             ,  minvalue = val ; 
              nextnode = 
                i;
               ]  
          , {i, 
              nn}
          ]; 
       currnode = 
            nextnode; 
       AppendTo[tour, 
            currnode]; 
     tourlength += 
            minvalue;  
  , {nn - 
              1}
   ]; 
     {tour, tourlength +  
            costs[[currnode + 1, 
                node + 1]]}
]

takebestheurtour := 
      Module[{tour, value, besttour, 
          bestvalue}, 
   {besttour, bestvalue} =  
          takeheurtour[1]; 
  Do[{tour, value} = 
            takeheurtour[i]; 
        If[
            value  <  bestvalue
        ,  
            bestvalue = 
              value; 
             besttour = 
              tour
             ]
     , {i, 2, 
            nn}
    ]; 
{besttour, 
          bestvalue}
]

generatebase provides a feasible base for an integral solution a represented as a list of arcs for which x=1; nn is the number of nodes

generatebase[a_,nn_]:=Block[{ab},
  k=1;
  arcnumberof=Table[0,{nn},{nn}];
  Do[arcnumberof[[i,j]]=k;
     arcnumberof[[j,i]]=k++,
  {i,nn-1},{j,i+1,nn}];
  MatrixForm[arcnumberof];
  eta2=Table[arcnumberof[[a[[i,1]],a[[i,2]]]],{i,Length[a]}];
  ab=Table[{i,i+1},{i,nn-1}];
  AppendTo[ab,{If[EvenQ[nn],2,1],nn}];
  base=Table[arcnumberof[[ab[[i,1]],ab[[i,2]]]],{i,Length[ab]}];
  eta2=Complement[eta2,Intersection[eta2,base]];
  eta1=Complement[Range[na],eta2,base];
  {base,eta1,eta2}
]

reoptimize:=Block[{},
index=m;
etato=1;
admissible=False;
While[!admissible,
tab=W.A;
q=index;
Block[{i,ratio,min},
      min = 1000000;
      If[etato==1
      ,
      Do[ k=eta1[[i]];
          If[tab[[q,k]]< - tolerance,
              ratio = cr[[k]]/(-tab[[q,k]]);
              If[ratio < min,
                 min = ratio; p = k;etafrom=1;ppos=i]
            ] 
        ,{i,Length[eta1]} 
       ];
       Do[ k=eta2[[i]];
           If[tab[[q,k]]>  tolerance,
              ratio = cr[[k]]/(-tab[[q,k]]);
              If[ratio < min,
                 min = ratio; p = k;etafrom=2;ppos=i]
            ] 
        ,{i,Length[eta2]} 
       ];
       ,
       Do[ k=eta1[[i]];
          If[tab[[q,k]]> tolerance,
              ratio = cr[[k]]/(tab[[q,k]]);
              If[ratio < min,
                 min = ratio; p = k;etafrom=1;ppos=i]
            ] 
        ,{i,Length[eta1]} 
       ];
       Do[ k=eta2[[i]];
           If[tab[[q,k]]< - tolerance,
              ratio = cr[[k]]/(tab[[q,k]]);
              If[ratio < min,
                 min = ratio; p = k;etafrom=2;ppos=i]
            ] 
        ,{i,Length[eta2]} 
       ];
       ]
];
pivot;
check;
];
Print["x= ",x];
]

check:=Block[{},
   exit=False;
   For[i=1,
       !exit,
       i++,
       exit=(i>Length[base]);
       If[!exit,
          admissible=((base[[i]]<=na) && (x[[i]]>=-tolerance) && (x[[i]]<=1+tolerance))
                      ||
                     ((base[[i]]>na) && (x[[i]]>=-tolerance));
         ];
       If[!admissible,index=i;
                      exit=True;
                      If[x[[i]]<0,etato=1,etato=2]
         ]
       ];
]

show[a_,b_,c_,d_]:=Block[{b1,dd1,dd2,dd3},
           Which[b==1,b1=0.005,b==2,b1=0.008,b==3,b1=0.015];
           Which[d=="R",dd1=1;dd2=0;dd3=0;,
                 d=="B",dd1=0;dd2=0;dd3=1;,
                 d=="G",dd1=0;dd2=1;dd3=0;,
                 d=="Y",dd1=1;dd2=1;dd3=0.5;,
                 d=="Bk",dd1=0;dd2=0;dd3=0;
                 ];
           If[c==0,
          Graphics[{Thickness[b1],RGBColor[dd1,dd2,dd3],
          Table[Line[{nodes[[a[[i,1]]]],
                         nodes[[a[[i,2]]]]}
                       ]
                   ,{i,Length[a]}]}],
          Graphics[{Thickness[b1],Dashing[{0.01}],RGBColor[dd1,dd2,dd3],
          Table[Line[{nodes[[a[[i,1]]]],
                         nodes[[a[[i,2]]]]}
                       ]
                   ,{i,Length[a]}]}]
                   ]]

simplex:=Block[{},
firstpivot;
entercolumn;
While[!optimal ,
       leavecolumn;
       pivot;
       entercolumn;
      ];
      
Print["x= ",x]];

leavecolumn:=
Block[{i,ratio,min},
      y = W . Transpose[A][[ p ]];
      If[etafrom==2,y=-y];
      min = 1000000;
      Block[{i,ratio,min},
      min = 1000000;
      Do[Which[y[[i]]>tolerance
               ,ratio = (x[[i]]-lb[[base[[i]]]])/y[[i]];
                If[ratio < min,
                   min = ratio; q = i;etato=1]
               ,y[[i]]<-tolerance
               ,ratio = (x[[i]]-ub[[base[[i]]]])/y[[i]];
                If[ratio < min,
                   min = ratio; q = i;etato=2]
               ];
         ,{i,m}     
        ];
      If[ub[[p]]-lb[[p]]<min,
          min=ub[[p]]-lb[[p]];etato=0]];
   ];

firstpivot:=Block[{},
B = Transpose[Transpose[A][[ base ]]];
W = Inverse[B];
cb = c[[ base ]];
Which[eta1=={}
     ,x = W. (b-Transpose[AT[[eta2]]].ub[[eta2]]);
      value=cb.x+c[[eta2]].ub[[eta2]]
     ,eta2=={}
     ,x = W. (b-Transpose[AT[[eta1]]].lb[[eta1]]);
      value=cb.x+c[[eta1]].lb[[eta1]]
     ,True
     ,x = W. (b-Transpose[AT[[eta2]]].ub[[eta2]]-
               -Transpose[AT[[eta1]]].lb[[eta1]]);
      value=cb.x+
         c[[eta2]].ub[[eta2]]+c[[eta1]].lb[[eta1]]
      ];
      Print[N[value]];
u = cb . W;
cr = c - u . A;]

pivot:=Block[{},
indexout=base[[q]];
Which[etato==1
     ,base[[q]]=p;
      If[etafrom==1
        ,eta1[[ppos]]=indexout
        ,eta2=Drop[eta2,{ppos,ppos}];
         eta1=Append[eta1,indexout]
        ]
     ,etato==2
     ,base[[q]]=p;
      If[etafrom==2
        ,eta2[[ppos]]=indexout
        ,eta1=Drop[eta1,{ppos,ppos}];
         eta2=Append[eta2,indexout]
        ]
     ,etato==0
     ,If[etafrom==1
        ,eta1=Drop[eta1,{ppos,ppos}];
         eta2=Append[eta2,p]
        ,eta2=Drop[eta2,{ppos,ppos}];
         eta1=Append[eta1,p]
        ]
     ];
B = Transpose[Transpose[A][[ base ]]];
W = Inverse[B];
cb = c[[ base ]];
Which[eta1=={}
     ,x = W. (b-Transpose[AT[[eta2]]].ub[[eta2]]);
      value=cb.x+c[[eta2]].ub[[eta2]]
     ,eta2=={}
     ,x = W. (b-Transpose[AT[[eta1]]].lb[[eta1]]);
      value=cb.x+c[[eta1]].lb[[eta1]]
     ,True
     ,x = W. (b-Transpose[AT[[eta2]]].ub[[eta2]]-
               -Transpose[AT[[eta1]]].lb[[eta1]]);
      value=cb.x+
         c[[eta2]].ub[[eta2]]+c[[eta1]].lb[[eta1]]
      ];
      Print[N[value]];
u = cb . W;
cr = c - u . A;]

entercolumn:=
   Block[{i},
         For[i=1,
             (i<=Length[eta1]) && 
             (cr[[eta1[[i]]]]>=-tolerance),
             i++, Null
            ];
          optimal=False;
         If[i==Length[eta1]+1,
            optimal=True,
            p=eta1[[i]];
            etafrom=1;
            ppos=i] ;
         If[optimal,
            For[i=1,
                (i<=Length[eta2]) && 
                (cr[[eta2[[i]]]]<=tolerance),
                i++, Null
               ];
            optimal=False;
            If[i==Length[eta2]+1,
               optimal=True,
               p=eta2[[i]];
               etafrom=2;
               ppos=i] ;
              ]  ;
        ];

addinequality:=Block[{a},
k=1;
ap=Table[0,{na}];
Do[If[MemberQ[nodeset,i]&&MemberQ[nodeset,j]
      ,ap[[k]]=1];
      k++;  
   ,{i,nn-1},{j,i+1,nn}];
cp=Floor[Length[nodeset]/2];
n=n+1;
A=Transpose[Append[Transpose[A],ap]];
c=Append[c,cp];
];

addsubtourrow:=Block[{a},
AppendTo[subtours,nodeset];
k=1;
row=Table[0,{n}];
Do[If[MemberQ[nodeset,i]&&MemberQ[nodeset,j]
      ,row[[k]]=1];
      k++;  
   ,{i,nn-1},{j,i+1,nn}];
newb=Length[nodeset]-1;
m=m+1;
n=n+1;
A=Append[A,row];
A=Transpose[Append[Transpose[A],Table[If[i==m,1,0],{i,m}]]];
AT=Transpose[A];
b=Append[b,newb];
c=Append[c,0];
lb=Append[lb,0];
ub=Append[ub,100000000];
W=Append[W,-row[[base]].W];
W=Transpose[Append[Transpose[W],Table[If[i==m,1,0],{i,m}]]];
base=Append[base,n];
B=Transpose[Transpose[A][[base]]];
newbase=True;
];

addcombrow:=Block[{a},
AppendTo[combs,{handle,teeth}];
k=1;
row=Table[0,{n}];
Do[If[(MemberQ[handle,i]&&MemberQ[handle,j]) ||
       Apply[Or,
           Table[MemberQ[teeth[[ii]],i]&&MemberQ[teeth[[ii]],j]
                 ,{ii,Length[teeth]}]]
      ,row[[k]]=1];
      k++;  
   ,{i,nn-1},{j,i+1,nn}];
newb=Length[handle]+Sum[Length[teeth[[i]]]-1,{i,Length[teeth]}]-
    (Length[teeth]+1)/2;
m=m+1;
n=n+1;
A=Append[A,row];
A=Transpose[Append[Transpose[A],Table[If[i==m,1,0],{i,m}]]];
AT=Transpose[A];
b=Append[b,newb];
c=Append[c,0];
lb=Append[lb,0];
ub=Append[ub,100000000];
W=Append[W,-row[[base]].W];
W=Transpose[Append[Transpose[W],Table[If[i==m,1,0],{i,m}]]];
base=Append[base,n];
B=Transpose[Transpose[A][[base]]];
newbase=True;
];

arctolist[a_] := 
      Module[{aa, k1, k2}, 
aa = 
          Sort[a]; 
{k1, k2} = 
          aa; (2 nn  - k1) (k1 - 1)/2 + k2 - k1]

addbranchrow[a_, v_] := 
      Module[{ind, row}, 
   ind = 
          arctolist[a]; 
   If[
          v == 0, 
        row = 
            Table[If[i == ind, 1, 0], {i, 
                n}]; 
        b = 
            Append[b, 
              v];
        , 
         row = 
            Table[If[i == ind, -1, 0], {i, 
                n}]; 
         b = 
            Append[b, -v];
    ] ; 
   m = m + 1; 
   n = 
          n + 1;     
   A = 
          Append[A, row]; 
   A = 
          Transpose[
            Append[Transpose[A], 
              Table[If[i == m, 1, 0], {i, 
                  m}]]]; 
   AT = 
          Transpose[A]; 
   c = 
          Append[c, 0]; 
  lb = 
          Append[lb, 0]; 
  ub = 
          Append[ub, 100000000]; 
  W = 
          Append[W, -row[[base]] . W]; 
  W = 
          Transpose[
            Append[Transpose[W], 
              Table[If[i == m, 1, 0], {i, 
                  m}]]]; 
  base = 
          Append[base, n]; 
  B = 
          Transpose[Transpose[
                A][[base]]]; 
  newbase = 
          True;
]

Data

Input mode n.1 
The arc costs are uniformly randomly  generated
between 1 and 99.
The graph nodes are represented on a circle.

nn=10;na=nn(nn-1)/2;

SeedRandom[10];

nodes=Table[5 {Sin[2 N[Pi]/nn i],Cos[2 N[Pi]/nn i]},{i,0,nn-1}];

bb=Table[Random[Integer,{1,99}],{na}]

costs=Table[0,{nn+1},{nn+1}];
k=1;
Do[costs[[1,i+1]]=i;costs[[i+1,1]]=i,{i,nn}];
Do[costs[[i+1,j+1]]=bb[[k]];
   costs[[j+1,i+1]]=bb[[k++]],
{i,nn-1},{j,i+1,nn}];
MatrixForm[costs]

rangeplot={{-5.6,5.6},{-6,6}};

aaa=Graphics[Table[{Point[nodes[[i]]],
      Text[ToString[i],nodes[[i]],0.5{-nodes[[i,1]],-nodes[[i,2]]}]},{i,Length[nodes]}]];

bbb=Graphics[Table[{Thickness[0.0002(100-costs[[i+1,j+1]])],
 Hue[  8/1000 costs[[i+1,j+1]]],
                    Line[{nodes[[i]],nodes[[j]]}]},
                   {i,nn-1},{j,i+1,nn}]];

next the arcs are displayed according to their values: the thickness is inversely proportional to the cost  (the thicker the better) and the color scale is as the light spectrum (from red to violet <--> from short to long arcs))

Show[aaa,bbb,AspectRatio->Automatic,
            PlotRange->rangeplot];

User provided initial tour for manual initialization (list of n nodes). The LP execution is faster if you initialize manually

starttour={9,6,5,7,8,4,1,3,10,2}

Length[starttour]

tourarcs=Table[{starttour[[i]],starttour[[i+1]]},
    {i,Length[starttour]-1}];
    AppendTo[ tourarcs,{starttour[[-1]],starttour[[1]]}];

length of tour

Apply[Plus, 
      MapThread[costs[[#1, #2]]  &,  
        Transpose[tourarcs + 1]]]

ccc=show[tourarcs,2,0,"B"];
Show[ccc,aaa,AspectRatio->Automatic,PlotRange->1.2 rangeplot];

Heuristic initial tour for manual initialization (list of n nodes). The LP execution is faster if you initialize manually

{starttour,value}=takebestheurtour

tourarcs=Table[{starttour[[i]],starttour[[i+1]]},
    {i,Length[starttour]-1}];
    AppendTo[ tourarcs,{starttour[[-1]],starttour[[1]]}];

ccc=show[tourarcs,2,0,"B"];
Show[ccc,aaa,AspectRatio->Automatic,PlotRange->1.2 rangeplot];

Input mode n.2
The arc costs are typed by the user (to be input as a vector; see the examples).
The graph nodes are represented on a circle.

Set #1

nn=8;
bb={1,1,10,10,10,10,10,
      1,10,10,10,10,10,
        10,10,10,10,10,
            1, 1, 1, 1,
               1, 1, 1,
                  1, 1,
                     1};

Set #2  (comb inequality)

nn=6;
bb={2, 2,10,10, 1,
       2,10, 1,10,
          1,10,10,
             2, 2,
                2};

Set #3

nn=12;
bb={1,2,9,2,9,3,9,9,9,9,9,
      9,2,9,2,9,3,9,9,9,9,
        1,2,9,9,9,3,9,9,9,
          9,2,9,9,9,3,9,9,
            1,9,9,9,9,3,9,
              9,9,9,9,9,3,
                1,2,9,2,9,
                  9,2,9,2,
                    1,2,9,
                      9,2,
                        1};

Setting-up data ( compulsory !)

na=nn(nn-1)/2;

nodes=Table[5 {Sin[2 N[Pi]/nn i],Cos[2 N[Pi]/nn i]},{i,0,nn-1}];

bmax=Max[bb];bmin=Min[ bb];bdiff= bmax-bmin ;

costs=Table[0,{nn+1},{nn+1}];
k=1;
Do[costs[[1,i+1]]=i;costs[[i+1,1]]=i,{i,nn}];
Do[costs[[i+1,j+1]]=bb[[k]];
   costs[[j+1,i+1]]=bb[[k++]],
{i,nn-1},{j,i+1,nn}];
MatrixForm[costs]

rangeplot={{-5.6,5.6},{-6,6}};

aaa=Graphics[Table[{Point[nodes[[i]]],
      Text[ToString[i],nodes[[i]],0.5{-nodes[[i,1]],-nodes[[i,2]]}]},
              {i,Length[nodes]}]];

bbb=Graphics[Table[{Thickness[0.02(bmax-costs[[i+1,j+1]])/bdiff],
 Hue[  8/10  (costs[[i+1,j+1]]-bmin)/bdiff],
                    Line[{nodes[[i]],nodes[[j]]}]},
                   {i,nn-1},{j,i+1,nn}]];

next the arcs are displayed according to their values: the thickness is inversely proportional to the cost  (the thicker the better) and the color scale is as the light spectrum (from red to violet <--> from short to long arcs))

Show[aaa,bbb,AspectRatio->Automatic,
            PlotRange->rangeplot];

Input mode n.3
First the nodes are randomly generated within a square.
Then the arc costs are taken as Euclidean distances.

nn is the number of nodes

nice seeds=40 (nn=10) -> fractional solution,
                 10 (nn=10) -> disjoint tours,
                 50 (nn=10) -> solution
                 30 (nn=10) -> two subtours
                 100 (nn=30) -> subtours and combs  
                 20 (nn=20) -> subtours and combs  
                 140 (nn=25) -> subtours and combs

SeedRandom[200]

nn=80;na=nn(nn-1)/2;

nodes={};marker=Table[False,{99},{99}];freespace=5;
Do[{n1,n2}={Random[Integer,{1,99}],Random[Integer,{1,99}]};
   While[marker[[n1,n2]],
        {n1,n2}={Random[Integer,{1,99}],Random[Integer,{1,99}]};
        ];
   AppendTo[nodes,{n1,n2}];
   Do[marker[[i,j]]=True,{i,Max[1,n1-freespace],Min[99,n1+freespace]},
                        {j,Max[1,n2-freespace],Min[99,n2+freespace]}  
     ];    
  ,{nn}]

nodes  (* coordinates *)

bb=Flatten[Table[Floor[N[Sqrt[(nodes[[i,1]]-nodes[[j,1]])^2+
                    (nodes[[i,2]]-nodes[[j,2]])^2]]],
           {i,nn-1},{j,i+1,nn}]];

costs=Table[0,{nn+1},{nn+1}];
k=1;
Do[costs[[1,i+1]]=i;costs[[i+1,1]]=i,{i,nn}];
Do[costs[[i+1,j+1]]=bb[[k]];
   costs[[j+1,i+1]]=bb[[k++]],
{i,nn-1},{j,i+1,nn}];
MatrixForm[costs];

rangeplot={{-5,105},{-5,105}};

aaa=Graphics[Table[{Point[nodes[[i]]],
      Text[ToString[i],nodes[[i]],{-2,0}]},{i,Length[nodes]}]];

aann = Graphics[Map[Point, nodes]];

bbb=Graphics[{Dashing[{0.01}],Table[Line[{nodes[[i]],nodes[[j]]}],
    {i,nn-1},{j,i+1,nn}]}];

Show[aaa,AspectRatio->Automatic,PlotRange->1.1 rangeplot];

User provided initial tour for manual initialization (list of n nodes)

starttour={1,3,2,5,6,4}

tourarcs=Table[{starttour[[i]],starttour[[i+1]]},
    {i,Length[starttour]-1}];
    AppendTo[ tourarcs,{starttour[[-1]],starttour[[1]]}]

length of tour

Apply[Plus, 
      MapThread[costs[[#1, #2]]  &,  
        Transpose[tourarcs + 1]]]

a={{1,2},{2,9},{9,5},{5,6},{6,3},{3,10},{10,4},{4,7},{7,8},{8,1}};

ccc=show[tourarcs,2,0,"B"];
Show[ccc,aaa,AspectRatio->Automatic,PlotRange->rangeplot];

Heuristic initial tour for manual initialization (list of n nodes). The LP execution is faster if you initialize manually

{starttour,value}=takebestheurtour

value

tourarcs=Table[{starttour[[i]],starttour[[i+1]]},
    {i,Length[starttour]-1}];
    AppendTo[ tourarcs,{starttour[[-1]],starttour[[1]]}];

ccc=show[tourarcs,2,0,"B"];
Show[ccc,aaa,AspectRatio->Automatic,PlotRange->1.2 rangeplot];

Input mode n.4
Euclidean instances generated by the user

Example #1

provide nn and  coordinates (between 1 and 100)

nn=12;na=nn(nn-1)/2;

nodes= 30 {{0,0.5},{0.5,0},{1,1},{0,2.5},{1,2},{0.5,3},
         {3,0.5},{2,1},{2.5,0},{2.5,3},{3,2.5},{2,2}}+5

bb=Flatten[Table[Floor[N[Sqrt[(nodes[[i,1]]-nodes[[j,1]])^2+
                    (nodes[[i,2]]-nodes[[j,2]])^2]]],
           {i,nn-1},{j,i+1,nn}]];

costs=Table[0,{nn+1},{nn+1}];
k=1;
Do[costs[[1,i+1]]=i;costs[[i+1,1]]=i,{i,nn}];
Do[costs[[i+1,j+1]]=bb[[k]];
   costs[[j+1,i+1]]=bb[[k++]],
{i,nn-1},{j,i+1,nn}];
MatrixForm[costs];

rangeplot={{-5,105},{-5,105}};

aaa=Graphics[Table[{Point[nodes[[i]]],
      Text[ToString[i],nodes[[i]],{-2,0}]},{i,Length[nodes]}]];

bbb=Graphics[{Dashing[{0.01}],Table[Line[{nodes[[i]],nodes[[j]]}],
    {i,nn-1},{j,i+1,nn}]}];

Show[aaa,AspectRatio->Automatic,PlotRange->rangeplot];

Example #2 (concentric points)

provide nn1, nn2 , nn3

nn1 = 10; nn2 = 15; nn3 = 20;

nn=nn1+nn2+nn3

na = nn (nn - 1)/2;

nodes1= Table[{50,50}+ 15. {Sin[2 N[Pi]/nn1 i],Cos[2 N[Pi]/nn1 i]},{i,0,nn1-1}];

nodes2= Table[{50,50}+ 30. {Sin[2 N[Pi]/nn2 i],Cos[2 N[Pi]/nn2 i]},{i,0,nn2-1}];

nodes3= Table[{50,50}+ 45. {Sin[2 N[Pi]/nn3 i],Cos[2 N[Pi]/nn3 i]},{i,0,nn3-1}];

nodes = Join[nodes1, nodes2, nodes3];

bb=Flatten[Table[Floor[N[Sqrt[(nodes[[i,1]]-nodes[[j,1]])^2+
                    (nodes[[i,2]]-nodes[[j,2]])^2]]],
           {i,nn-1},{j,i+1,nn}]];

costs=Table[0,{nn+1},{nn+1}];
k=1;
Do[costs[[1,i+1]]=i;costs[[i+1,1]]=i,{i,nn}];
Do[costs[[i+1,j+1]]=bb[[k]];
   costs[[j+1,i+1]]=bb[[k++]],
{i,nn-1},{j,i+1,nn}];
MatrixForm[costs];

rangeplot={{-5,105},{-5,105}};

aaa=Graphics[Table[{Point[nodes[[i]]],
      Text[ToString[i],nodes[[i]],{-2,0}]},{i,Length[nodes]}]];

bbb=Graphics[{Dashing[{0.01}],Table[Line[{nodes[[i]],nodes[[j]]}],
    {i,nn-1},{j,i+1,nn}]}];

Show[aaa,AspectRatio->Automatic,PlotRange->rangeplot];

Example #3 (many combs)

provide nn1 and   nn2

nn1 = 8 ;nn2 =  4 ;

nn=  nn1+nn2

na = nn (nn - 1)/2;

nodes1= Table[{50,50}+ 45. {Sin[2  N[Pi]/nn1 i], Cos[ 2 N[Pi]/nn1 i]},{i,1,nn1 }];

nodes2= Table[ {50,50+(i ) (80/nn2)} ,{i,-Round[nn2/2],nn2-1-Round[nn2/2]}];

nodes = Join[nodes1, nodes2 ];

bb=Flatten[Table[Floor[N[Sqrt[(nodes[[i,1]]-nodes[[j,1]])^2+
                    (nodes[[i,2]]-nodes[[j,2]])^2]]],
           {i,nn-1},{j,i+1,nn}]];

costs=Table[0,{nn+1},{nn+1}];
k=1;
Do[costs[[1,i+1]]=i;costs[[i+1,1]]=i,{i,nn}];
Do[costs[[i+1,j+1]]=bb[[k]];
   costs[[j+1,i+1]]=bb[[k++]],
{i,nn-1},{j,i+1,nn}];
MatrixForm[costs];

rangeplot={{-5,105},{-5,105}};

aaa=Graphics[Table[{Point[nodes[[i]]],
      Text[ToString[i],nodes[[i]],{-2,0}]},{i,Length[nodes]}]];

bbb=Graphics[{Dashing[{0.01}],Table[Line[{nodes[[i]],nodes[[j]]}],
    {i,nn-1},{j,i+1,nn}]}];

Show[aaa,AspectRatio->Automatic,PlotRange->rangeplot];

Example #4 -  irregular mesh

provide nn1 and nn2   --  mesh

nn1 = 5;nn2 = 4;

nn=  nn1 nn2

na = nn (nn - 1)/2;

nodes = 
        Flatten[Table[{i 100/(nn1 + 1), j 100/(nn2 + 1)}, {j, nn2, 
              1, -1}, {i, nn1}], 1];

nodes = 
        Map[{#[[1]] + (50/(nn1 + 1)) 
                  Random[], #[[2]] + (50/(nn2 + 1)) Random[]} &, 
          nodes];

bb=Flatten[Table[Floor[N[Sqrt[(nodes[[i,1]]-nodes[[j,1]])^2+
                    (nodes[[i,2]]-nodes[[j,2]])^2]]],
           {i,nn-1},{j,i+1,nn}]];

costs=Table[0,{nn+1},{nn+1}];
k=1;
Do[costs[[1,i+1]]=i;costs[[i+1,1]]=i,{i,nn}];
Do[costs[[i+1,j+1]]=bb[[k]];
   costs[[j+1,i+1]]=bb[[k++]],
{i,nn-1},{j,i+1,nn}];
MatrixForm[costs];

rangeplot={{-5,105},{-5,105}};

aaa=Graphics[Table[{Point[nodes[[i]]],
      Text[ToString[i],nodes[[i]],{-2,-2}]},{i,Length[nodes]}]];

bbb=Graphics[{Dashing[{0.01}],Table[Line[{nodes[[i]],nodes[[j]]}],
    {i,nn-1},{j,i+1,nn}]}];

Show[aaa,AspectRatio->Automatic,PlotRange->rangeplot];

User provided initial tour for manual initialization (list of n nodes)

starttour={1,3,2,5,6,4}

tourarcs=Table[{starttour[[i]],starttour[[i+1]]},
    {i,Length[starttour]-1}];
    AppendTo[ tourarcs,{starttour[[-1]],starttour[[1]]}]

length of tour

Apply[Plus, 
      MapThread[costs[[#1, #2]]  &,  
        Transpose[tourarcs + 1]]]

a={{1,2},{2,9},{9,5},{5,6},{6,3},{3,10},{10,4},{4,7},{7,8},{8,1}};

ccc=show[tourarcs,2,0,"B"];
Show[ccc,aaa,AspectRatio->Automatic,PlotRange->rangeplot];

Heuristic initial tour for manual initialization (list of n nodes). The LP execution is faster if you initialize manually

{starttour,value}=takebestheurtour

tourarcs=Table[{starttour[[i]],starttour[[i+1]]},
    {i,Length[starttour]-1}];
    AppendTo[ tourarcs,{starttour[[-1]],starttour[[1]]}];

length of tour

Apply[Plus, 
      MapThread[costs[[#1, #2]]  &,  
        Transpose[tourarcs + 1]]]

ccc=show[tourarcs,2,0,"B"];
Show[ccc,aaa,AspectRatio->Automatic,PlotRange->1.2 rangeplot];

Input mode n.5
Non complete graphs - Hamiltonian tours

provide node coordinates

nodes=  {{0,0},{10, 30},{80, 70},{0, 90 },{50,50},{90,0},
         {30,70},{60,0},{70,20},{30,30},{90,90},{60,90}}

aaa=Graphics[{ PointSize[.03],Table[{Point[nodes[[i]]],
Text[ToString[i],nodes[[i]]+3 ]  },{i,Length[nodes]}]}];
Show[aaa, AspectRatio->Automatic, PlotRange->All];

provide arcs and costs  (  {  { { i , j }, cost arc ij} , ..... }   )

fullarcs={{ {1,2},2},{ {1,8},5},{ {2,7},6},{ {1,4},1},{ {2,5},7},{ {2,8},10},{ {4,12},5},{ {7,12},8},{ {12,11},3},{ {2,10},5},{ {7,3},8},{ {5,3},9},{ {3,11},6},{ {5,9},2},{ {10,9},4},{ {10,5},7},{ {8,6},7},{ {9,6},6},{ {4,7},10},{ {9,3},1},{ {6,11},10}};

arcs = Transpose[fullarcs][[1]]

bbb=Graphics[{RGBColor[0,0,1],Table[
      Line[{nodes[[arcs[[i,1]]]],nodes[[arcs[[i,2]]]]}],
    {i,Length[arcs]}]}];

Show[aaa,bbb,AspectRatio->Automatic,
      PlotRange->All];

allarcs = 
        Flatten[Table[{i, j}, {i, nn - 1}, {j, i + 1, nn}], 1];

nonarcs = Complement[allarcs, Map[Sort, arcs]];

allfullarcs = 
        Sort[Join[
            Transpose[{Map[Sort, arcs], Transpose[fullarcs][[2]]}], 
            Transpose[{nonarcs, 
                Table[10^5, {Length[nonarcs]}]}]] ];

bb = Transpose[allfullarcs][[2]];

costs=Table[0,{nn+1},{nn+1}];
k=1;
Do[costs[[1,i+1]]=i;costs[[i+1,1]]=i,{i,nn}];
Do[costs[[i+1,j+1]]=bb[[k]];
   costs[[j+1,i+1]]=bb[[k++]],
{i,nn-1},{j,i+1,nn}];
MatrixForm[costs];

Heuristic initial tour for manual initialization (list of n nodes). The LP execution is faster if you initialize manually

{starttour,value}=takebestheurtour

value

tourarcs=Table[{starttour[[i]],starttour[[i+1]]},
    {i,Length[starttour]-1}];
    AppendTo[ tourarcs,{starttour[[-1]],starttour[[1]]}];

ccc=show[tourarcs,2,0,"B"];
Show[ccc,aaa,AspectRatio->Automatic,PlotRange->All];

Input mode n.  6
Non complete graphs - non Hamiltonian tours

provide node coordinates

nodes=  {{0,0},{10, 30},{80, 70},{0, 90 },{50,50},{90,0},
         {30,70},{60,0},{70,20},{30,30},{90,90},{60,90}}

aaa=Graphics[{ PointSize[.03],Table[{Point[nodes[[i]]],
Text[ToString[i],nodes[[i]]+3 ]  },{i,Length[nodes]}]}];
Show[aaa, AspectRatio->Automatic, PlotRange->All];

provide arcs and costs  (  {  {cost arc ij, { i , j }} , ..... }   )

fullarcs={{ {1,2},2},{ {1,8},5},{ {2,7},6},{ {1,4},1},{ {2,5},7},{ {2,8},10},{ {4,12},5},{ {7,12},8},{ {12,11},3},{ {2,10},5},{ {7,3},8},{ {5,3},9},{ {3,11},6},{ {5,9},2},{ {10,9},4},{ {10,5},7},{ {8,6},7},{ {9,6},6},{ {4,7},10},{ {9,3},1},{ {6,11},10}};

arcs = Transpose[fullarcs][[1]]

bbb=Graphics[{RGBColor[0,0,1],Table[
      Line[{nodes[[arcs[[i,1]]]],nodes[[arcs[[i,2]]]]}],
    {i,Length[arcs]}]}];

Show[aaa,bbb,AspectRatio->Automatic,
      PlotRange->All];

allarcs = 
        Flatten[Table[{i, j}, {i, nn - 1}, {j, i + 1, nn}], 1];

nonarcs = Complement[allarcs, Map[Sort, arcs]];

allfullarcs = 
        Sort[Join[
            Transpose[{Map[Sort, arcs], Transpose[fullarcs][[2]]}], 
            Transpose[{nonarcs, 
                Table[10^5, {Length[nonarcs]}]}]] ];

bb = Transpose[allfullarcs][[2]];

costs=Table[0,{nn },{nn }];
k=1;
Do[costs[[i ,j ]]=bb[[k]];
   costs[[j ,i ]]=bb[[k++]],
{i,nn-1},{j,i+1,nn}];
MatrixForm[costs] ;

spcosts = costs;
pntable = Table[i, {i, nn}, {j, nn}];
Do[Do [ 
        If[spcosts[[i, j]] >  
            spcosts[[i, k]] + 
              spcosts[[k, 
                  j]], 
                    spcosts[[i, j]] =  
            spcosts[[i, k]] + 
              spcosts[[k, 
                  j]]    ; 
                       pntable[[i, j]]  = pntable[[k, j]] ]  , {i, 
          nn}, {j, nn}], {k, nn}]

k=1;
Do[bb[[k]]=spcosts[[i ,j ]] ;
   bb[[k++]]=spcosts[[j ,i ]] ,
{i,nn-1},{j,i+1,nn}];
bb ;

costs=Table[0,{nn+1},{nn+1}];
k=1;
Do[costs[[1,i+1]]=i;costs[[i+1,1]]=i,{i,nn}];
Do[costs[[i+1,j+1]]=bb[[k]];
   costs[[j+1,i+1]]=bb[[k++]],
{i,nn-1},{j,i+1,nn}];
MatrixForm[costs];

MatrixForm[spcosts];

Heuristic initial tour for manual initialization (list of n nodes). The LP execution is faster if you initialize manually

{starttour,value}=takebestheurtour

value

tourarcs=Table[{starttour[[i]],starttour[[i+1]]},
    {i,Length[starttour]-1}];
    AppendTo[ tourarcs,{starttour[[-1]],starttour[[1]]}];

ccc=show[tourarcs,2,0,"B"];
Show[ccc,aaa,AspectRatio->Automatic,PlotRange->All];

Input mode n.  7
Instances derived by Hamiltonian circuit problems

Seeds : 	(nn=10)
            23

nn=20;na=nn(nn-1)/2;

SeedRandom[23];
nodes=Table[5 {Sin[2 N[Pi]/nn i],Cos[2 N[Pi]/nn i]},{i,0,nn-1}];

d=4;
prob=d/(nn-1);
arcs={};
bb={};
Do[If[Random[]<prob,AppendTo[arcs,{i,j}];AppendTo[bb,0]
                   ,AppendTo[bb,1]]
                   ,{i,1,nn-1},{j,i+1,nn}]

arcs  (*list of arcs*)

bb

bbb=Graphics[{RGBColor[0,0,1],Table[
      Line[{nodes[[arcs[[i,1]]]],nodes[[arcs[[i,2]]]]}],
    {i,Length[arcs]}]}];

rangeplot={{-7,7},{-6,6}};

aaa=Graphics[{PointSize[0.02],Table[{Point[nodes[[i]]],
      Text[ToString[i],nodes[[i]],0.5{-nodes[[i,1]],-nodes[[i,2]]}]},{i,Length[nodes]}]}];
      Show[aaa,bbb,AspectRatio->Automatic,
      PlotRange->rangeplot];

Possible addition of arcs (to be repeated if needed). Then execute again the graphical statements above

newarc = {6, 5}

AppendTo[arcs, newarc];
bb[[arctolist[newarc]]] = 1;

Input mode n.  8
Other instances

Italian regional headtowns

nn=20;na=nn(nn-1)/2;

nodes=
{{48, 61}, {1, 88}, {47, 48}, {76, 35}, {31, 73}, {58, 39},
 {31, 64},  {11, 72}, {15, 84}, {55, 31}, {47, 1}, {39, 56},
  {67, 29}, {68, 1}, {40, 42}, {3, 80}, {31, 90}, {50, 85},
   {47, 89}, {39, 82}};

bb =  {610,195,465,215,325,320,510,425,390,1110,165,460,875,285,545,440,445,415,305,
       795,1065,395,925,470,245,180,955,1675,625,1100,1440,745,110,400,585,550,445,
               400,400,190,375,600,610,245,965,175,390,730,110,730,625,630,600,490,
                  670,220,720,945,880,260,690,610,145,455,450,1000,895,900,870,760,
                     530,105,295,210,590,1310,260,735,1075,380,330,225,295,260,155,
                           490,720,740,135,825,385,200,590,225,860,755,760,725,620,
                              225,300,490,1205,155,630,970,280,395,315,395,365,255,
                                140,715,1430,380,860,1195,505,170,370,540,505,400,
                                     785,1505,455,930,1270,575,140,245,410,380,270,
                                           735,380,155,500,220,885,800,880,850,740,
                                         1100,680,235,935,1600,1520,1600,1570,1460,
                                                   525,865,170,550,470,480,450,340,
                                                      445,360,1030,945,895,865,755,
                                                      700,1365,1285,1365,1335,1225,                                     
                                                               675,590,670,640,530,
                                                                   355,540,510,400,
                                                                       285,225,195,
                                                                            75,155,
                                                                               125};

costs=Table[0,{nn+1},{nn+1}];
k=1;
Do[costs[[1,i+1]]=i;costs[[i+1,1]]=i,{i,nn}];
Do[costs[[i+1,j+1]]=bb[[k]];
   costs[[j+1,i+1]]=bb[[k++]],
{i,nn-1},{j,i+1,nn}];
MatrixForm[costs];

rangeplot={{-5,81},{-5,95}};

aaa=Graphics[Table[{Point[nodes[[i]]],
      Text[ToString[i],nodes[[i]],{-2,0}]},{i,Length[nodes]}]];

bbb=Graphics[{Dashing[{0.01}],Table[Line[{nodes[[i]],nodes[[j]]}],
    {i,nn-1},{j,i+1,nn}]}];

Show[aaa,AspectRatio->Automatic,PlotRange->rangeplot];

boot strings

a hamiltonian path on a complete euclidean bipartite graph (nn must be even!)

nn=20; na=nn(nn-1)/2;;

nodes= Join[Table[{0,nn/2 - i+1},{i,nn/2}],Table[{10,  i },{i,nn/2}]]

costs=Table[0,{nn },{nn }];
Do[Do[ costs[[i,nn/2+j]] = Floor[10 Sqrt[(nodes[[i]]-nodes[[nn/2+j]]).(nodes[[i]]-nodes[[nn/2+j]])]];costs[[nn/2+j,i]]=costs[[i,nn/2+j]] ,{j,nn/2}],{i,nn/2}];
Do[costs[[i,j]]=10^3;costs[[nn/2+i,nn/2+j]]=10^3,{i,nn/2},{j,nn/2}];
costs[[1,nn]]=0;costs[[nn,1]]=0;
MatrixForm[costs] ;

bb=Flatten[Table[costs[[i,j]],
           {i,nn-1},{j,i+1,nn}]] ;

costs = 
        Prepend[Transpose[Prepend[ costs , Range[nn]]], 
          Prepend[Range[nn], 0]];

rangeplot={{-5,81},{-5,95}};

aaa=Graphics[{Table[{Point[nodes[[i]]],
Text[ToString[i],nodes[[i]],{ 2,0}]},{i,nn/2}],Table[{Point[nodes[[i]]],Text[ToString[i],nodes[[i]],{-2,0}]},{i,nn/2+1,nn}]}];

bbb=Graphics[{Dashing[{0.01}],Table[Line[{nodes[[i]],nodes[[j]]}],
    {i,nn-1},{j,i+1,nn}]}];

Show[aaa,AspectRatio->Automatic,PlotRange->All];

Heuristic initial tour for manual initialization (list of n nodes). The LP execution is faster if you initialize manually

{starttour,value}=takebestheurtour

value

tourarcs=Table[{starttour[[i]],starttour[[i+1]]},
    {i,Length[starttour]-1}];
    AppendTo[ tourarcs,{starttour[[-1]],starttour[[1]]}];

ccc=show[tourarcs,2,0,"B"];
Show[ccc,aaa,AspectRatio->Automatic,PlotRange->All];

User provided initial tour for manual initialization (list of n nodes)

starttour={2,9,17,19,18,20,5,1,12,3,6,4,13,14,11,10,15,7,8,16}

tourarcs=Table[{starttour[[i]],starttour[[i+1]]},
    {i,Length[starttour]-1}];
    AppendTo[ tourarcs,{starttour[[-1]],starttour[[1]]}]

ccc=show[tourarcs,2,0,"B"];
Show[ccc,aaa,AspectRatio->Automatic,PlotRange->rangeplot];

Input mode n. 9  - Multiple tours from a common depot
The nodes are randomly generated within a square.
The arc costs are taken as Euclidean distances.

nn is the number of nodes  - 1  is the depot

SeedRandom[100]

tournumber = 3;

nn=30;

nodes={};marker=Table[False,{99},{99}];freespace=5;
Do[{n1,n2}={Random[Integer,{1,99}],Random[Integer,{1,99}]};
   While[marker[[n1,n2]],
        {n1,n2}={Random[Integer,{1,99}],Random[Integer,{1,99}]};
        ];
   AppendTo[nodes,{n1,n2}];
   Do[marker[[i,j]]=True,{i,Max[1,n1-freespace],Min[99,n1+freespace]},
                        {j,Max[1,n2-freespace],Min[99,n2+freespace]}  
     ];    
  ,{nn}]

nodes  (* coordinates *)

Do[AppendTo[nodes, nodes[[1]]], {tournumber - 1}]

nn = nn + tournumber - 1 ; na = nn (nn - 1)/2;

bb=Flatten[Table[Floor[N[Sqrt[(nodes[[i,1]]-nodes[[j,1]])^2+
                    (nodes[[i,2]]-nodes[[j,2]])^2]]],
           {i,nn-1},{j,i+1,nn}]];

Do[bb[[nn - i]] = 10^5,  {i, tournumber - 1}]; 
    cliquesize = (tournumber - 1) (tournumber - 2)/2; 
    Do[bb[[-i]] = 10^5, {i, cliquesize}]

costs=Table[0,{nn+1},{nn+1}];
k=1;
Do[costs[[1,i+1]]=i;costs[[i+1,1]]=i,{i,nn}];
Do[costs[[i+1,j+1]]=bb[[k]];
   costs[[j+1,i+1]]=bb[[k++]],
{i,nn-1},{j,i+1,nn}];
MatrixForm[costs];

rangeplot={{-5,105},{-5,105}};

aaa=Graphics[{Table[{Point[nodes[[i]]],
Text[ToString[i],nodes[[i]],{-2,0}]},{i,Length[nodes]-tournumber+1}],Table[Text[ToString[1],nodes[[-i]],{-2,0}],{i,tournumber-1}]}];

aann = Graphics[Map[Point, nodes]];

bbb=Graphics[{Dashing[{0.01}],Table[Line[{nodes[[i]],nodes[[j]]}],
    {i,nn-1},{j,i+1,nn}]}];

Show[aaa,AspectRatio->Automatic,PlotRange->1.1 rangeplot];

User provided initial tour for manual initialization (list of n nodes)

starttour={1,3,2,5,6,4}

tourarcs=Table[{starttour[[i]],starttour[[i+1]]},
    {i,Length[starttour]-1}];
    AppendTo[ tourarcs,{starttour[[-1]],starttour[[1]]}]

length of tour

Apply[Plus, 
      MapThread[costs[[#1, #2]]  &,  
        Transpose[tourarcs + 1]]]

a={{1,2},{2,9},{9,5},{5,6},{6,3},{3,10},{10,4},{4,7},{7,8},{8,1}};

ccc=show[tourarcs,2,0,"B"];
Show[ccc,aaa,AspectRatio->Automatic,PlotRange->rangeplot];

Heuristic initial tour for manual initialization (list of n nodes). The LP execution is faster if you initialize manually

{starttour,value}=takebestheurtour

value

tourarcs=Table[{starttour[[i]],starttour[[i+1]]},
    {i,Length[starttour]-1}];
    AppendTo[ tourarcs,{starttour[[-1]],starttour[[1]]}];

ccc=show[tourarcs,2,0,"B"];
Show[ccc,aaa,AspectRatio->Automatic,PlotRange->1.2 rangeplot];

Computation

LP initialization (must be done in any case; choose one of the two options)

Initialization from scratch

n=na;m=nn;
A=Table[0,{i,nn},{j,na}];
base={};
eta1={};
k=1;
Do[A[[i,k]]=1;A[[j,k]]=1;
   If[i+1==j,AppendTo[base,k],AppendTo[eta1,k]];
   k++;
   ,{i,nn-1},{j,i+1,nn}];
A=N[A];
AT=N[Transpose[A]];
AppendTo[base,2];
eta1=Drop[eta1,{nn-2,nn-2}];
eta1=Drop[eta1,1];
eta2={nn-1};
c=bb;
b=Table[2,{nn}];
lb=Table[0,{na}];
ub=Table[1,{na}];
newbase=True;
i=.;arclist={};
     k=1;
     Do[AppendTo[arclist,{i,j}];
      k++,
        {i,nn-1},{j,i+1,nn}];
subtours={};combs={};
tolerance=0.001;

Initialization from an initial tour (requires providing a tour as a list  tourarcs of arcs)

{base,eta1,eta2}=generatebase[tourarcs,nn];
n=na;m=nn;
A=Table[0,{i,nn},{j,na}];
k=1;
Do[A[[i,k]]=1;A[[j,k]]=1; k++;
   ,{i,nn-1},{j,i+1,nn}];
A=N[A];
AT=N[Transpose[A]];
c=bb;
b=Table[2,{nn}];
lb=Table[0,{na}];
ub=Table[1,{na}];
newbase=True;
i=.;arclist={};
     k=1;
     Do[AppendTo[arclist,{i,j}];
      k++,
        {i,nn-1},{j,i+1,nn}];
subtours={};combs={};
tolerance=0.001;

LP run (not for precooked instances)

current objective printouts (degeneracy!)

simplex

Precooked instances (these are large instances whose first LP has been already solved and the optimal base is stored here)

To run precooked instances you need:

-- generating the data of the corresponding instance
-- running the LP initialization - Automatic or Manual
-- NOT doing LP run
-- reading the base,eta1,eta2 data below for the instance
-- computing 'do this for any optimal base'
-- computing solution below

Italian regional headtowns

base=
{190, 104, 131, 40, 185, 4, 94, 61, 157, 100, 2, 
120, 147, 186, 64, 132, 138, 187, 63, 26};

eta1=
{149, 57, 10, 107, 109, 23, 28, 20, 21, 77, 60, 36, 126, 12, 48, 6, 137, 
 
  112, 8, 81, 16, 13, 50, 51, 43, 53, 52, 59, 84, 58, 18, 32, 80, 19, 71, 
 
  62, 66, 67, 68, 69, 70, 1, 55, 37, 45, 78, 79, 9, 76, 7, 164, 42, 27, 
 
  15, 125, 88, 29, 24, 95, 96, 97, 98, 99, 102, 54, 105, 128, 106, 75, 35, 
 
  176, 93, 87, 117, 118, 115, 119, 14, 121, 123, 124, 155, 129, 130, 111, 
 
  122, 135, 22, 127, 83, 39, 141, 91, 143, 144, 145, 30, 86, 46, 150, 151, 
 
  152, 153, 154, 31, 5, 158, 116, 133, 161, 159, 47, 165, 166, 167, 168, 
 
  169, 171, 172, 173, 174, 175, 177, 178, 179, 180, 182, 183, 108, 181, 
 
  184, 156, 38, 65, 56, 103, 146, 17, 110, 114, 142, 90, 160, 44, 162, 
 
  170, 134, 3, 139, 41, 73, 74, 136, 101, 34, 140, 163, 92, 85, 25};

eta2=
{11, 89, 148, 188, 33, 113, 49, 82, 189, 72};

Euclidean instance, 30 nodes (seed 30)

base=
{1, 30, 58, 85, 111, 136, 160, 183, 205, 226, 246, 265, 
283, 300, 316, 331, 345, 358, 370, 381, 391, 400,
 408, 415, 421, 426, 430, 433, 435, 57};

eta1=
{2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 
15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29};

eta2=
{7, 25, 47, 48, 76, 78, 94, 106, 115, 125, 
140, 158, 176, 208, 211, 227, 252, 267, 285,
 312, 327, 349, 350, 369, 375, 378, 392, 423};

Euclidean instance, 50 nodes (seed 10)

base = {1022, 659, 473, 710, 283, 39, 90, 551, 155, 911, 1056, 1112, 
          262, 948, 279, 
451, 108, 200, 145, 402, 939, 
          969, 575, 759, 1001, 286, 1090, 206, 1089, 441, 
          387, 
769, 412, 904, 432, 
          357, 
1181, 490, 13, 989, 1140, 602, 1153, 702, 
          495, 1187, 927, 544, 890, 1205};

eta1 = {272, 1225, 4, 273, 542, 8, 351, 11, 12, 14, 1150, 17, 957, 
          20, 484, 1135, 
26, 84, 5, 557, 1052, 31, 32, 33, 
          34, 382, 1147, 439, 820, 37, 40, 41, 1169, 
1014, 
          46, 47, 418, 51, 52, 260, 194, 176, 50, 105, 310, 59, 524, 583, 49, 
          631, 
1219, 65, 66, 67, 69, 472, 71, 73, 993, 75, 
          68, 1023, 62, 79, 72, 81, 76, 1121, 
239, 122, 
          1171, 88, 1190, 872, 1216, 1050, 94, 1223, 953, 165, 98, 99, 103, 
          1166, 
106, 107, 100, 109, 111, 112, 734, 114, 
          115, 116, 117, 77, 875, 363, 121, 598, 
123, 125, 
          126, 127, 128, 129, 110, 906, 130, 133, 78, 135, 136, 594, 295, 
          144, 
134, 141, 142, 736, 138, 146, 3, 148, 149, 
          150, 186, 151, 153, 292, 581, 156, 
157, 154, 
          159, 779, 163, 164, 166, 167, 168, 158, 170, 172, 173, 174, 175, 
          171, 
177, 178, 179, 180, 181, 182, 183, 184, 
          185, 113, 187, 188, 189, 190, 449, 193, 
406, 
          195, 196, 191, 198, 199, 201, 202, 221, 204, 210, 828, 209, 211, 
          212, 213, 
214, 215, 197, 217, 218, 219, 220, 
          192, 222, 223, 224, 225, 226, 227, 228, 
          229, 
230, 231, 232, 233, 234, 235, 268, 259, 
          241, 237, 244, 245, 247, 248, 249, 250, 
251, 
          240, 253, 254, 255, 256, 257, 258, 243, 261, 1214, 263, 265, 266, 
          238, 236, 
269, 270, 271, 277, 274, 242, 276, 44, 
          278, 152, 54, 284, 285, 282, 281, 288, 
289, 302, 
          291, 308, 280, 287, 147, 296, 101, 298, 299, 300, 303, 321, 304, 
          305, 
306, 307, 301, 309, 293, 290, 313, 314, 
          315, 316, 317, 1031, 319, 320, 312, 322, 
1, 323, 
          326, 327, 329, 325, 331, 332, 333, 334, 335, 336, 337, 663, 339, 
          341, 86, 
343, 205, 345, 346, 347, 348, 349, 421, 
          352, 350, 353, 739, 355, 356, 642, 984, 
360, 
          361, 362, 364, 899, 56, 365, 393, 369, 370, 367, 372, 371, 374, 
          375, 376, 
377, 366, 379, 380, 381, 383, 384, 
          385, 1194, 386, 391, 392, 373, 394, 395, 
          396, 
216, 398, 399, 400, 401, 1103, 390, 404, 
          264, 407, 408, 465, 410, 435, 433, 411, 
414, 
          415, 416, 417, 419, 119, 422, 423, 424, 1070, 426, 427, 428, 429, 
          430, 413, 
431, 434, 23, 436, 437, 571, 444, 442, 
          443, 27, 843, 446, 447, 169, 294, 450, 
453, 454, 
          455, 456, 458, 459, 460, 461, 462, 463, 58, 466, 467, 468, 469, 
          470, 
471, 452, 10, 474, 475, 476, 477, 478, 479, 
          481, 482, 464, 483, 486, 485, 488, 
489, 491, 
          492, 499, 487, 493, 496, 497, 498, 510, 500, 501, 502, 504, 494, 
          506, 
507, 505, 509, 508, 511, 512, 513, 514, 
          515, 516, 517, 518, 519, 520, 521, 522, 
60, 523, 
          526, 527, 528, 529, 530, 531, 532, 533, 534, 535, 1220, 537, 538, 
          539, 
540, 541, 545, 546, 664, 548, 549, 405, 
          552, 553, 554, 555, 556, 558, 388, 397, 
61, 561, 
          564, 560, 567, 160, 569, 420, 85, 572, 573, 574, 565, 576, 577, 
          578, 
579, 580, 566, 19, 563, 562, 586, 587, 588, 
          589, 590, 592, 593, 585, 595, 597, 
596, 599, 
          616, 570, 536, 604, 605, 606, 607, 608, 609, 610, 132, 612, 613, 
          614, 
615, 600, 617, 618, 619, 620, 621, 622, 
          623, 624, 625, 626, 627, 628, 629, 630, 
525, 
          633, 634, 635, 636, 637, 632, 639, 641, 640, 330, 643, 644, 645, 
          646, 647, 
648, 649, 650, 651, 653, 655, 15, 657, 
          654, 660, 661, 662, 63, 656, 666, 667, 
668, 669, 
          696, 671, 672, 673, 674, 675, 676, 559, 678, 679, 681, 682, 683, 
          684, 
665, 686, 687, 688, 689, 685, 691, 692, 
          677, 694, 695, 16, 638, 698, 715, 874, 
703, 704, 
          705, 701, 707, 708, 709, 25, 711, 712, 713, 714, 699, 716, 706, 
          718, 
719, 720, 721, 722, 723, 724, 725, 726, 
          727, 728, 729, 731, 732, 733, 568, 1198, 
737, 
          738, 457, 740, 741, 742, 743, 744, 745, 747, 730, 749, 748, 751, 
          752, 753, 
754, 755, 756, 757, 758, 328, 760, 
          717, 761, 786, 766, 767, 768, 770, 771, 
          772, 
773, 774, 775, 764, 777, 778, 763, 762, 
          781, 782, 783, 784, 785, 789, 787, 788, 
780, 
          790, 1081, 793, 805, 795, 794, 797, 798, 799, 796, 801, 802, 803, 
          804, 944, 
806, 161, 808, 809, 810, 811, 812, 
          813, 814, 815, 816, 817, 818, 819, 821, 
          833, 
823, 824, 825, 21, 827, 38, 829, 830, 831, 
          832, 807, 834, 835, 836, 837, 838, 
839, 840, 
          841, 842, 826, 844, 845, 846, 847, 1173, 848, 849, 852, 853, 850, 
          862, 
45, 857, 859, 543, 861, 854, 851, 864, 865, 
          22, 867, 868, 869, 856, 866, 873, 
863, 860, 877, 
          879, 880, 881, 882, 883, 884, 885, 9, 887, 888, 889, 886, 
          891, 
892, 893, 894, 440, 896, 897, 898, 140, 
          900, 902, 903, 74, 905, 915, 907, 908, 
909, 910, 
          901, 912, 913, 24, 924, 916, 917, 918, 919, 920, 921, 922, 923, 
          776, 
925, 926, 928, 930, 931, 932, 933, 934, 
          929, 936, 937, 938, 940, 941, 942, 943, 
120, 
          945, 946, 947, 1042, 949, 951, 950, 955, 952, 64, 958, 959, 1093, 
          961, 962, 
963, 960, 965, 966, 967, 968, 972, 
          971, 964, 973, 975, 976, 977, 978, 979, 
          982, 
981, 980, 983, 974, 985, 986, 987, 378, 
          324, 990, 991, 992, 139, 994, 996, 997, 
998, 
          999, 1000, 1002, 995, 1004, 1003, 1006, 1007, 1008, 1009, 1010, 
          1011, 1012, 
1013, 1005, 1015, 1017, 1016, 1019, 
          1020, 1018, 1034, 870, 1024, 1026, 1027, 
          252, 
1029, 1030, 1025, 1032, 1033, 1021, 1035, 
          42, 1038, 30, 1039, 1041, 1040, 1043, 
1044, 
          1045, 1037, 1047, 1048, 1049, 1036, 1046, 1053, 1054, 858, 871, 
          1058, 
1059, 1055, 1061, 1062, 1063, 1060, 1065, 
          1066, 1067, 1068, 1064, 1071, 1072, 
1073, 1076, 
          1075, 1078, 1079, 1080, 445, 1082, 1083, 1084, 670, 1086, 
          1087, 
1088, 1085, 1091, 1092, 935, 1094, 1095, 
          1096, 1097, 1098, 1099, 1100, 1101, 
970, 1104, 
          1105, 1107, 1106, 1109, 1110, 1077, 82, 1113, 1114, 1115, 
          1116, 
1102, 547, 1119, 1108, 83, 1123, 1122, 
          1125, 1126, 1127, 1128, 1129, 1130, 1131, 
1132, 
          1124, 1134, 1136, 1138, 1139, 1137, 1141, 1133, 1144, 1145, 1142, 
          582, 
1148, 267, 1149, 1152, 1197, 1154, 1155, 
          1156, 1157, 1158, 43, 1161, 1162, 1163, 
1164, 
          1165, 29, 1167, 1168, 55, 1170, 1172, 87, 1160, 1176, 1174, 1177, 
          1178, 
1180, 1182, 1183, 1184, 1185, 1186, 91, 
          1188, 1211, 89, 1192, 1193, 1215, 1196, 
95, 
          1120, 1203, 1201, 1202, 1191, 1200, 2, 1207, 1208, 96, 1206, 1212, 
          1213, 
1209, 1217, 1218, 1221, 1189, 1224, 1175, 
          1222, 1146, 28, 1051, 611, 92, 914, 
690, 1151, 
          297, 1143, 800, 143, 118, 735, 208, 1159, 1118, 403, 93, 35, 7, 
          1210, 
340, 368, 1028, 358, 131, 104, 1199, 70, 
          1204, 36, 275, 697, 603, 792, 895, 1057, 
1117, 
          1111, 6, 203, 425, 956, 680, 791, 822, 80, 344, 750, 1069, 354, 
          338, 318, 
57, 988, 342, 137, 591, 246, 409, 
          448};

eta2 = {162, 311, 503, 550, 652, 658, 746, 765, 855, 1195, 693, 954, 
          584, 1074, 
102, 480, 700, 207, 601, 438, 389, 
          878, 1179, 359, 97, 124, 876, 48, 53, 18};

Euclidean instance, 20 nodes (seed 20)

base = {182, 12, 46, 151, 90, 108, 80, 171, 43, 56, 187, 114, 23, 84, 
          87, 37, 165, 15, 127, 32};

eta1 = {133, 21, 1, 5, 4, 7, 9, 10, 6, 18, 14, 16, 167, 52, 19, 35, 
          53, 47, 24, 3, 101, 8, 30, 31, 33, 137, 173, 181, 20, 40, 79, 105, 
          44, 45, 39, 38, 49, 51, 129, 48, 54, 55, 61, 59, 60, 29, 122, 63, 
          62, 65, 64, 67, 69, 70, 72, 81, 71, 74, 77, 75, 78, 36, 82, 83, 76, 
          25, 88, 86, 92, 93, 94, 91, 95, 98, 99, 160, 103, 102, 104, 107, 
          106, 109, 111, 112, 100, 156, 22, 117, 11, 119, 118, 121, 97, 73, 
          26, 126, 125, 130, 128, 132, 131, 135, 138, 143, 140, 139, 142, 
          141, 144, 145, 147, 150, 
149, 148, 152, 153, 
          146, 157, 155, 159, 158, 161, 162, 164, 176, 166, 168, 169, 
          170, 
172, 185, 174, 175, 177, 178, 113, 183, 
          184, 186, 189, 188, 17, 190, 123, 27, 66, 
          58, 
41, 154, 42, 28, 85, 115, 96, 124, 2, 120, 
          179};

eta2 = {180, 68, 110, 136, 163, 34, 89, 57, 134, 13, 50, 
          116};

Euclidean instance, 50 nodes (seed 100)

base = {287, 619, 311, 398, 209, 539, 268, 50, 637, 807, 659, 
          112, 1025, 1143, 1033, 1071, 874, 437, 503, 565, 730, 30, 522, 
          1161, 172, 775, 1127, 980, 713, 580, 896, 672, 1066, 542, 323, 166, 
          853, 123, 1178, 465, 116, 338, 691, 971, 231, 919, 417, 816, 467, 
          799};

eta1 = {43, 4, 1015, 6, 7, 8, 831, 17, 13, 5, 36, 77, 1221, 558, 3, 
          557, 18, 21, 23, 16, 14, 26, 
27, 24, 491, 15, 
          31, 480, 9, 82, 25, 35, 38, 28, 39, 1, 42, 41, 44, 193, 40, 48, 45, 
          145, 52, 100, 274, 55, 56, 33, 230, 399, 424, 483, 22, 626, 98, 
          658, 463, 249, 99, 103, 71, 241, 73, 426, 75, 29, 251, 79, 74, 
          1053, 83, 84, 960, 961, 1171, 963, 964, 956, 1205, 1203, 1044, 958, 
          95, 96, 72, 243, 101, 102, 62, 410, 128, 93, 196, 111, 67, 1218, 
          113, 1162, 115, 118, 119, 120, 121, 122, 564, 124, 126, 127, 130, 
          131, 224, 1166, 132, 135, 134, 137, 138, 106, 141, 142, 143, 239, 
          51, 147, 148, 149, 150, 186, 152, 151, 154, 155, 156, 157, 158, 
          159, 160, 153, 162, 163, 164, 165, 965, 168, 169, 180, 171, 948, 
          174, 175, 176, 177, 146, 179, 748, 181, 182, 183, 300, 185, 1034, 
          187, 660, 761, 190, 206, 987, 194, 195, 240, 212, 198, 199, 200, 
          201, 202, 203, 204, 205, 221, 207, 208, 210, 923, 197, 213, 214, 
          215, 216, 257, 219, 220, 228, 92, 223, 133, 225, 217, 227, 211, 
          192, 20, 229, 232, 233, 234, 235, 836, 245, 512, 64, 242, 750, 585, 
          633, 246, 791, 247, 250, 877, 780, 53, 248, 191, 252, 255, 254, 
          253, 256, 259, 260, 261, 262, 263, 264, 1140, 266, 267, 281, 269, 
          258, 272, 273, 271, 276, 277, 278, 279, 54, 315, 283, 284, 285, 
          286, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 
          318, 97, 302, 303, 304, 305, 306, 307, 308, 309, 310, 282, 312, 
          280, 301, 621, 316, 1100, 313, 319, 320, 321, 322, 341, 358, 326, 
          327, 328, 329, 330, 331, 332, 333, 334, 324, 336, 337, 237, 335, 
          340, 339, 353, 343, 344, 345, 346, 347, 348, 349, 1130, 352, 342, 
          354, 355, 356, 244, 325, 359, 361, 362, 363, 364, 1200, 367, 368, 
          369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 382, 
          365, 384, 385, 386, 387, 394, 389, 390, 275, 388, 393, 381, 395, 
          392, 397, 366, 396, 400, 402, 403, 404, 405, 406, 408, 407, 413, 
          412, 409, 414, 441, 416, 418, 419, 420, 421, 415, 57, 411, 425, 
          434, 427, 428, 422, 430, 423, 432, 431, 429, 433, 436, 438, 435, 
          314, 439, 442, 443, 444, 445, 58, 448, 478, 451, 452, 453, 454, 10, 
          456, 114, 458, 459, 460, 117, 447, 446, 464, 466, 461, 477, 469, 
          470, 468, 473, 462, 471, 472, 476, 455, 449, 105, 474, 475, 482, 
          481, 479, 516, 518, 487, 489, 490, 178, 501, 34, 494, 110, 496, 
          497, 498, 49, 500, 502, 499, 504, 505, 1223, 457, 506, 509, 508, 
          511, 513, 514, 515, 108, 517, 486, 32, 520, 521, 524, 60, 526, 527, 
          528, 107, 531, 552, 533, 523, 525, 536, 537, 532, 529, 549, 541, 
          559, 543, 544, 545, 546, 534, 548, 538, 550, 551, 535, 173, 554, 
          553, 37, 555, 574, 562, 560, 563, 567, 568, 569, 570, 571, 561, 
          573, 595, 575, 583, 577, 578, 566, 579, 582, 581, 584, 572, 586, 
          587, 588, 576, 590, 591, 589, 593, 594, 61, 597, 609, 599, 600, 
          601, 109, 603, 604, 605, 606, 602, 607, 598, 610, 611, 612, 613, 
          608, 615, 614, 617, 618, 596, 616, 440, 623, 620, 624, 627, 628, 
          629, 630, 631, 698, 641, 488, 636, 634, 638, 639, 640, 63, 643, 
          635, 644, 632, 646, 647, 655, 649, 650, 651, 652, 657, 645, 642, 
          654, 653, 656, 648, 661, 662, 663, 664, 666, 693, 665, 669, 670, 
          671, 673, 667, 675, 676, 677, 678, 679, 680, 681, 682, 683, 684, 
          685, 686, 674, 688, 689, 690, 692, 687, 694, 695, 668, 697, 718, 
          721, 700, 703, 704, 705, 699, 707, 702, 709, 706, 711, 712, 729, 
          710, 716, 715, 65, 717, 720, 719, 722, 723, 724, 714, 726, 727, 
          728, 725, 129, 732, 733, 734, 735, 736, 739, 738, 731, 740, 741, 
          742, 743, 737, 760, 744, 747, 749, 746, 751, 752, 753, 754, 755, 
          756, 66, 778, 759, 758, 769, 763, 764, 765, 766, 762, 768, 771, 
          770, 790, 772, 773, 19, 774, 777, 776, 779, 592, 781, 782, 783, 
          767, 785, 485, 784, 786, 789, 788, 798, 793, 792, 809, 68, 797, 
          1087, 819, 801, 161, 803, 802, 805, 806, 794, 808, 795, 810, 811, 
          812, 796, 814, 804, 800, 815, 813, 493, 821, 822, 823, 820, 825, 
          540, 827, 824, 829, 830, 828, 843, 833, 834, 832, 999, 835, 838, 
          837, 840, 841, 842, 69, 844, 845, 846, 847, 867, 850, 865, 863, 
          854, 849, 856, 851, 495, 848, 861, 852, 855, 860, 866, 862, 859, 
          857, 869, 870, 871, 872, 873, 864, 876, 875, 878, 879, 880, 881, 
          883, 884, 885, 401, 888, 889, 890, 891, 892, 882, 868, 895, 894, 
          897, 898, 818, 900, 80, 903, 904, 902, 906, 924, 908, 909, 910, 
          907, 912, 911, 914, 916, 917, 918, 913, 920, 905, 922, 921, 901, 
          925, 927, 939, 218, 929, 943, 928, 933, 934, 935, 930, 937, 938, 
          950, 940, 941, 140, 1146, 944, 1208, 946, 947, 942, 949, 951, 952, 
          953, 1062, 1073, 1110, 1106, 957, 89, 85, 86, 87, 88, 1181, 1198, 
          967, 90, 969, 1173, 959, 970, 974, 975, 976, 977, 978, 979, 981, 
          982, 973, 984, 985, 986, 983, 988, 989, 990, 991, 992, 993, 994, 
          995, 997, 1004, 136, 1074, 1001, 1002, 998, 1007, 1005, 1006, 996, 
          1008, 1009, 1010, 1011, 1012, 1013, 1014, 1003, 1029, 1017, 1019, 
          1020, 1021, 1022, 170, 1024, 1026, 1027, 1028, 1023, 1030, 1016, 
          1018, 1031, 1220, 1035, 1036, 1038, 1039, 1040, 1048, 1041, 78, 
          1043, 1045, 1046, 1047, 1042, 1049, 1050, 125, 1052, 1051, 1056, 
          1057, 1058, 1065, 1060, 1061, 1063, 1064, 1059, 1088, 1067, 1068, 
          1069, 1070, 1072, 1090, 1079, 1075, 1083, 1078, 1076, 1080, 1081, 
          955, 945, 1084, 1077, 1086, 1082, 144, 1091, 1092, 81, 1093, 1095, 
          1096, 1094, 1098, 1099, 839, 1101, 1102, 1103, 1104, 1105, 1107, 
          1109, 1000, 1111, 1112, 1113, 1114, 1115, 1108, 1120, 1118, 1119, 
          1116, 1122, 886, 1124, 1125, 1126, 1128, 1129, 1123, 1131, 1132, 
          1133, 1134, 1136, 1135, 936, 1139, 1138, 1141, 1142, 1137, 1144, 
          1145, 1121, 1147, 1148, 1150, 1151, 1152, 1153, 1154, 1149, 1190, 
          1159, 1155, 1160, 2, 1164, 972, 1167, 1168, 1169, 1170, 1163, 962, 
          1172, 1175, 1176, 1177, 1174, 1179, 1180, 139, 1183, 1182, 968, 
          1186, 1187, 1188, 1189, 1191, 1197, 1158, 1194, 1195, 1196, 1193, 
          1199, 966, 1201, 1202, 1225, 1204, 91, 94, 1206, 1210, 1212, 1213, 
          1214, 1215, 1217, 1216, 1219, 1207, 59, 1224, 1089, 1085, 899, 47, 
          265, 893, 1055, 226, 351, 357, 350, 1117, 1097, 1222, 1032, 787, 
          12, 519, 931, 188, 104, 510, 238, 757, 507, 1211, 46, 1192, 696, 
          189, 547, 167, 817, 317, 826, 484, 184, 1185, 926, 492, 625, 391, 
          1037, 70, 708};

eta2 = {11, 701, 887, 383, 1157, 1209, 360, 222, 236, 270, 745, 1165, 
          450, 530, 932, 1054, 
1156, 954, 556, 915, 858, 
          622, 1184, 76};

Euclidean instance, 80 nodes (seed 200)

base = {1774, 851, 2120, 2835, 608, 681, 2093, 1671, 1545, 2281, 224, 
          2784, 778, 75, 2887, 1582, 461, 2416, 1856, 2019, 2049, 1378, 2515, 
          351, 2154, 1464, 1206, 310, 816, 465, 1950, 46, 457, 1527, 2137, 
          693, 1137, 1570, 1356, 2018, 2193, 214, 1358, 2214, 1760, 2652, 
          1396, 3056, 1300, 1768, 2041, 2753, 2186, 1065, 1266, 1621, 876, 
          1868, 129, 1799, 1498, 2628, 1240, 1585, 68, 62, 1505, 2356, 1536, 
          3122, 564, 260, 1928, 703, 436, 950, 1244, 491, 2334, 
          598};

eta1 = {2, 5, 6, 4, 7, 12, 9, 15, 1517, 1054, 18, 1446, 21, 22, 23, 
          1781, 27, 29, 30, 1391, 32, 1152, 35, 36, 37, 3, 39, 40, 41, 42, 
          19, 44, 1261, 38, 2694, 49, 1182, 51, 52, 131, 1459, 55, 56, 1757, 
          58, 59, 60, 61, 45, 1, 3160, 2729, 53, 1663, 50, 69, 47, 72, 73, 
          1074, 3155, 3159, 3094, 3153, 82, 386, 483, 85, 651, 745, 88, 317, 
          90, 91, 1079, 1081, 94, 95, 1014, 97, 98, 1208, 101, 103, 1288, 
          105, 106, 107, 108, 109, 111, 1937, 2172, 2034, 2293, 2335, 2663, 
          119, 2086, 2506, 122, 123, 124, 125, 878, 2696, 16, 128, 2264, 130, 
          133, 238, 135, 2691, 442, 139, 169, 143, 118, 145, 132, 3115, 3073, 
          3125, 150, 151, 152, 153, 154, 77, 156, 159, 158, 161, 162, 163, 
          164, 165, 246, 167, 168, 1080, 170, 171, 172, 173, 174, 175, 176, 
          213, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 
          190, 191, 192, 193, 194, 195, 196, 198, 199, 200, 201, 202, 203, 
          204, 205, 207, 218, 209, 210, 1567, 212, 439, 208, 216, 217, 96, 
          219, 220, 221, 222, 223, 446, 225, 226, 227, 228, 229, 230, 231, 
          215, 233, 234, 235, 280, 294, 239, 81, 241, 464, 236, 244, 268, 
          245, 247, 248, 250, 251, 252, 253, 255, 256, 257, 243, 259, 261, 
          262, 258, 264, 265, 120, 267, 274, 269, 237, 271, 2814, 273, 460, 
          242, 276, 277, 278, 438, 270, 281, 1888, 283, 301, 285, 286, 287, 
          288, 289, 290, 284, 291, 293, 292, 2292, 296, 297, 298, 299, 300, 
          295, 302, 2183, 282, 305, 308, 307, 306, 309, 380, 311, 909, 315, 
          316, 166, 2872, 319, 312, 313, 314, 323, 324, 321, 326, 327, 328, 
          329, 322, 331, 332, 333, 334, 335, 337, 338, 330, 340, 341, 342, 
          343, 339, 345, 346, 347, 348, 370, 350, 352, 320, 354, 355, 356, 
          357, 358, 359, 360, 349, 362, 363, 364, 365, 366, 367, 344, 369, 
          318, 371, 372, 368, 374, 375, 376, 377, 378, 353, 379, 381, 382, 
          383, 384, 385, 459, 388, 443, 390, 391, 392, 393, 394, 389, 396, 
          397, 398, 399, 400, 387, 414, 403, 404, 405, 406, 407, 408, 409, 
          410, 31, 412, 413, 232, 422, 416, 417, 418, 419, 420, 421, 3027, 
          423, 424, 425, 426, 427, 451, 429, 430, 395, 432, 433, 434, 435, 
          437, 99, 2960, 440, 441, 428, 449, 444, 445, 1410, 447, 448, 431, 
          206, 415, 452, 453, 454, 455, 456, 458, 70, 472, 84, 463, 498, 466, 
          517, 462, 469, 470, 471, 514, 473, 474, 475, 476, 361, 478, 479, 
          480, 481, 482, 467, 484, 485, 486, 487, 488, 489, 477, 520, 493, 
          494, 495, 490, 497, 468, 499, 496, 501, 502, 503, 504, 505, 506, 
          507, 509, 510, 511, 512, 513, 534, 500, 516, 402, 518, 519, 521, 
          522, 523, 524, 525, 515, 527, 528, 529, 530, 531, 532, 1462, 535, 
          1674, 533, 538, 589, 539, 541, 542, 543, 1960, 545, 546, 547, 548, 
          549, 550, 551, 568, 553, 554, 555, 556, 557, 558, 559, 560, 561, 
          544, 563, 537, 565, 566, 567, 570, 569, 552, 571, 249, 573, 574, 
          575, 576, 577, 578, 579, 580, 581, 582, 583, 584, 585, 604, 588, 
          587, 590, 591, 592, 593, 594, 595, 596, 607, 599, 600, 601, 602, 
          603, 572, 606, 3145, 86, 615, 609, 612, 613, 614, 611, 616, 617, 
          618, 619, 620, 621, 622, 623, 624, 625, 605, 627, 628, 660, 630, 
          631, 632, 633, 629, 636, 637, 638, 837, 640, 8, 642, 979, 644, 645, 
          646, 647, 648, 649, 650, 960, 652, 653, 654, 655, 656, 657, 643, 
          659, 658, 661, 662, 2126, 664, 665, 666, 667, 668, 641, 670, 671, 
          672, 673, 674, 675, 676, 705, 679, 87, 682, 683, 684, 685, 686, 
          687, 688, 680, 690, 691, 692, 677, 694, 240, 696, 697, 698, 699, 
          700, 701, 702, 715, 704, 709, 706, 678, 708, 689, 711, 712, 713, 
          714, 739, 716, 717, 718, 719, 720, 721, 722, 723, 536, 725, 724, 
          137, 730, 729, 728, 731, 732, 733, 734, 735, 736, 737, 695, 726, 
          740, 741, 742, 743, 744, 1827, 752, 746, 749, 750, 748, 753, 2024, 
          755, 756, 757, 758, 76, 1491, 761, 762, 799, 764, 1180, 766, 767, 
          769, 770, 771, 772, 773, 774, 775, 776, 777, 747, 779, 781, 806, 
          783, 784, 785, 786, 787, 788, 789, 754, 791, 810, 793, 794, 795, 
          796, 780, 798, 790, 800, 801, 43, 1109, 804, 805, 797, 807, 808, 
          2498, 811, 812, 803, 814, 89, 14, 819, 820, 821, 822, 823, 824, 
          825, 842, 827, 828, 829, 826, 831, 1102, 833, 834, 835, 830, 1088, 
          838, 839, 832, 836, 846, 843, 844, 845, 840, 847, 848, 849, 850, 
          815, 852, 853, 854, 855, 64, 857, 856, 858, 860, 859, 862, 863, 
          864, 861, 866, 2149, 868, 869, 870, 871, 872, 873, 874, 865, 877, 
          879, 880, 881, 48, 943, 883, 886, 887, 889, 888, 890, 891, 892, 
          893, 894, 895, 896, 931, 898, 899, 885, 901, 902, 903, 904, 905, 
          906, 907, 900, 949, 910, 911, 912, 884, 914, 897, 916, 913, 918, 
          919, 920, 921, 922, 923, 924, 926, 927, 928, 929, 930, 915, 917, 
          933, 937, 935, 936, 934, 938, 939, 940, 941, 942, 932, 944, 945, 
          946, 947, 948, 818, 952, 953, 954, 955, 956, 1007, 958, 959, 961, 
          962, 1035, 964, 957, 966, 963, 968, 967, 971, 972, 969, 974, 975, 
          976, 977, 978, 951, 980, 973, 965, 983, 2601, 985, 986, 987, 988, 
          984, 990, 991, 992, 993, 994, 995, 996, 997, 998, 999, 981, 1001, 
          1002, 1003, 1004, 1005, 1006, 13, 1008, 813, 71, 1010, 1013, 1012, 
          2188, 1017, 1063, 1018, 1019, 1021, 1022, 1023, 1020, 1024, 1026, 
          1027, 1255, 1029, 759, 1046, 1032, 1033, 1028, 92, 1036, 1037, 
          1038, 1031, 1040, 1041, 1042, 1043, 1016, 1045, 1030, 2632, 1034, 
          1039, 1050, 2782, 1052, 1053, 1055, 1056, 1057, 1058, 1048, 1060, 
          1051, 1062, 1061, 1064, 1066, 1067, 1068, 1069, 1070, 1071, 1072, 
          1073, 1059, 2772, 610, 1077, 1078, 1075, 126, 93, 1153, 1082, 1085, 
          1086, 1087, 1084, 1089, 1090, 1091, 1083, 1093, 1138, 1095, 1096, 
          1129, 1098, 1099, 1100, 1101, 2259, 1103, 1105, 540, 1107, 1108, 
          1104, 1110, 1111, 1112, 1113, 1144, 1115, 1116, 1117, 1118, 1119, 
          1120, 1121, 1122, 1123, 1124, 1125, 1127, 1128, 1097, 1130, 1131, 
          1132, 1133, 1134, 1135, 1136, 1114, 1139, 1140, 1141, 1142, 1143, 
          707, 1146, 2852, 1148, 1149, 1150, 1151, 1199, 1154, 1155, 1432, 
          1157, 1158, 1159, 1160, 1171, 1162, 1163, 1164, 1165, 1166, 1167, 
          1230, 1169, 1170, 1147, 1172, 1670, 1174, 1175, 1176, 1177, 1860, 
          1179, 1264, 1181, 1183, 1184, 792, 1186, 1187, 1188, 1189, 104, 
          1191, 751, 1193, 1161, 1192, 1196, 1197, 1198, 1195, 1200, 1201, 
          1203, 1145, 1205, 1194, 1207, 1173, 1212, 1213, 1214, 2243, 1209, 
          1217, 1252, 1219, 1220, 1211, 1222, 1221, 1224, 1225, 1226, 1227, 
          1228, 1229, 1223, 1231, 1232, 1233, 1234, 1235, 1236, 1237, 1238, 
          1239, 1241, 2113, 1243, 3080, 1245, 1246, 17, 1248, 1249, 1250, 
          1251, 2397, 1253, 1254, 2526, 2847, 1257, 2249, 1259, 1260, 1215, 
          1262, 1263, 3074, 1265, 1258, 1267, 1269, 1271, 1272, 20, 1270, 
          1275, 1276, 1277, 1278, 1279, 1281, 1282, 1796, 1284, 1285, 304, 
          1287, 1289, 1564, 1291, 1274, 1293, 1290, 1295, 1296, 1297, 1298, 
          1299, 1301, 1106, 1303, 1304, 1305, 1306, 1315, 1308, 1294, 1310, 
          1312, 1307, 1314, 1313, 1316, 1317, 1318, 1319, 1320, 1321, 1322, 
          1323, 1324, 1325, 1326, 1327, 1328, 1329, 1309, 1331, 1333, 1334, 
          1336, 1337, 1332, 1385, 1340, 1335, 1338, 1343, 1342, 1345, 1346, 
          1347, 1339, 1375, 1348, 1351, 1352, 1353, 1354, 1355, 1357, 1350, 
          1359, 1360, 1362, 1382, 1364, 1365, 1361, 1367, 1368, 1369, 1370, 
          1371, 1372, 1363, 1374, 1373, 1376, 1377, 765, 1379, 1380, 1381, 
          2124, 1383, 1384, 1366, 1386, 1387, 1388, 1389, 1390, 1392, 1393, 
          1394, 1395, 1397, 1676, 1399, 1400, 1504, 1402, 1403, 1404, 1405, 
          1447, 1407, 1408, 1409, 1398, 1411, 1412, 411, 1414, 1415, 1416, 
          1413, 1418, 1419, 54, 1421, 1420, 1423, 1256, 1425, 1448, 57, 1428, 
          1429, 1430, 1431, 1422, 1433, 1434, 1216, 1437, 1438, 1439, 1440, 
          1417, 1442, 1443, 1444, 1445, 1441, 1426, 1406, 1449, 1451, 1450, 
          1453, 1452, 1455, 1456, 1490, 1458, 1457, 1460, 1461, 1494, 1463, 
          1465, 1466, 1467, 1468, 1469, 1470, 1471, 1472, 1473, 1474, 1475, 
          2162, 1477, 1478, 1479, 1480, 1481, 1482, 1483, 1476, 1485, 1486, 
          1487, 1488, 1489, 1454, 1499, 1492, 1493, 401, 1495, 1496, 1497, 
          1349, 1500, 1501, 1502, 1503, 1484, 663, 1506, 1507, 1509, 1510, 
          2420, 1210, 1513, 1514, 1515, 1516, 1511, 1518, 1519, 1521, 1508, 
          1523, 1524, 1525, 1512, 127, 1528, 1529, 1530, 1531, 1532, 1533, 
          1522, 1535, 1526, 1537, 2761, 1539, 1540, 1541, 1542, 1543, 1544, 
          3054, 1546, 1547, 1548, 1549, 1550, 1551, 1552, 1553, 1555, 1538, 
          1557, 1558, 1559, 1560, 1561, 1562, 1563, 1556, 1566, 1565, 1534, 
          1569, 1571, 1572, 1574, 1575, 1590, 1577, 1576, 1579, 1580, 1581, 
          1583, 1584, 1586, 1587, 1588, 1589, 1578, 1591, 1592, 1593, 1594, 
          1595, 1596, 1597, 1598, 1605, 1600, 1620, 1602, 1603, 1604, 1599, 
          1606, 1607, 1608, 1609, 1610, 1611, 1612, 1614, 1615, 1616, 1617, 
          1618, 1619, 1601, 2037, 102, 1622, 1625, 802, 1623, 1628, 1624, 
          1630, 1631, 1632, 1627, 28, 1635, 1636, 1637, 1638, 1640, 1633, 
          2819, 1634, 1642, 1645, 1646, 1647, 1648, 1649, 1650, 1669, 1652, 
          1653, 1654, 1655, 1656, 1657, 1658, 1659, 1834, 1661, 1662, 1664, 
          1626, 1665, 1666, 1644, 1668, 1651, 1667, 1643, 1672, 1673, 2155, 
          1675, 1677, 1679, 1680, 2029, 1682, 1681, 841, 1685, 1686, 1687, 
          1688, 1689, 1690, 1691, 1692, 1641, 1694, 1683, 782, 1695, 2368, 
          1699, 1268, 1701, 1702, 1703, 1704, 1705, 1706, 1707, 1708, 1709, 
          1710, 1711, 1697, 1713, 1700, 1715, 1716, 1698, 1684, 1719, 1720, 
          2254, 1722, 1723, 1714, 1717, 1727, 1721, 1729, 1730, 1733, 1732, 
          1735, 1736, 1737, 1738, 1739, 1740, 1741, 1742, 1731, 1744, 1745, 
          1734, 1747, 1748, 1749, 1746, 1751, 1752, 1765, 1754, 1753, 1756, 
          114, 1758, 2857, 1761, 1762, 1763, 1764, 1755, 1759, 2131, 1771, 
          3016, 1770, 1780, 1772, 1766, 1750, 1775, 1776, 1777, 1778, 1401, 
          1773, 1779, 1782, 1783, 1785, 1786, 26, 1788, 1789, 1790, 1791, 
          1787, 1828, 1795, 1793, 1797, 1798, 1804, 1800, 1801, 1802, 1009, 
          1803, 1805, 1806, 1807, 1808, 1809, 1810, 1811, 1812, 1784, 1814, 
          1813, 1819, 1818, 1846, 1820, 1821, 1822, 1823, 1824, 1825, 1826, 
          1817, 1829, 1830, 1831, 1832, 1833, 1815, 1835, 1838, 1837, 1840, 
          1841, 1842, 1843, 1836, 1845, 2418, 1847, 1848, 1844, 1850, 1853, 
          1852, 1851, 1854, 1855, 1849, 1857, 1427, 1859, 1884, 1861, 1862, 
          1863, 1864, 1865, 1866, 1867, 1869, 2240, 1839, 1872, 1871, 1881, 
          1875, 1876, 1873, 1878, 1879, 2161, 1870, 1877, 1883, 1882, 1885, 
          1887, 3001, 1889, 1886, 1890, 1892, 266, 1895, 1894, 1896, 1905, 
          1898, 1899, 2457, 1901, 1902, 1903, 1904, 1292, 1906, 1893, 1908, 
          1909, 1910, 1911, 1907, 1913, 1912, 1915, 1920, 1917, 1914, 1919, 
          1918, 1921, 1922, 1923, 1924, 1925, 1926, 1927, 2051, 1929, 1930, 
          1931, 1932, 1933, 1934, 1916, 2015, 1936, 1979, 1940, 1941, 1942, 
          1939, 1948, 1945, 1946, 1947, 626, 1949, 1969, 1951, 1944, 1953, 
          1954, 1955, 1956, 1957, 1958, 1959, 1938, 1961, 1962, 1963, 1964, 
          1965, 1966, 1978, 1968, 1984, 1970, 1971, 1973, 1974, 1975, 1967, 
          1977, 1976, 1952, 1943, 1981, 1982, 1983, 1980, 1985, 2030, 1988, 
          1990, 1991, 1992, 112, 1994, 1995, 1986, 1997, 1998, 1999, 2000, 
          2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 1987, 2010, 2011, 
          2012, 2013, 2014, 1993, 2016, 2017, 2009, 2020, 2021, 2022, 2846, 
          1996, 2025, 2026, 2027, 2028, 2299, 2023, 2031, 2032, 146, 2036, 
          2033, 110, 2038, 2040, 2039, 2042, 2043, 2328, 2045, 2046, 2047, 
          2048, 2050, 272, 2052, 2053, 2054, 2055, 2056, 2057, 1613, 2059, 
          3042, 2061, 2062, 2063, 2058, 2065, 2066, 2067, 2068, 2069, 2070, 
          2071, 597, 2073, 2074, 2075, 2076, 2077, 2078, 2044, 2081, 2080, 
          2082, 325, 2083, 2064, 2087, 2088, 2085, 2090, 2084, 1726, 2094, 
          2092, 2095, 2097, 2096, 2099, 2100, 2098, 2102, 2103, 2104, 2105, 
          2106, 2107, 2117, 2109, 2110, 2111, 2112, 2091, 2114, 2115, 2116, 
          2108, 2118, 2119, 2101, 2121, 2123, 2122, 2125, 1767, 2035, 2129, 
          2130, 2169, 2132, 2133, 2128, 2135, 2136, 2127, 2138, 1011, 2140, 
          2141, 2142, 2143, 2145, 2146, 2147, 2148, 639, 2150, 2151, 2152, 
          1858, 2918, 2134, 2156, 1280, 2158, 1874, 2160, 2659, 2950, 2163, 
          2164, 2165, 34, 2157, 2168, 2167, 1049, 2171, 2173, 2170, 2175, 
          2174, 2177, 2176, 2179, 2180, 2181, 2182, 279, 2178, 2185, 2060, 
          2187, 2606, 2189, 2190, 2192, 2191, 2194, 2196, 2197, 2198, 2199, 
          2200, 2201, 2202, 2203, 2204, 2205, 2206, 2207, 2208, 2209, 2210, 
          2211, 2212, 2213, 2184, 2216, 2217, 2153, 2219, 2220, 2215, 2222, 
          2223, 2497, 2225, 2224, 2227, 2228, 2229, 2230, 2226, 2232, 2233, 
          2231, 2235, 2236, 2237, 2238, 2239, 2218, 2241, 2242, 2244, 2234, 
          2245, 2246, 2247, 2221, 2250, 2251, 2252, 2253, 450, 2255, 2256, 
          2257, 115, 2260, 2262, 2263, 2258, 2265, 2266, 2267, 2268, 2269, 
          2270, 2271, 2272, 2273, 2274, 2275, 2276, 2277, 2278, 2279, 2284, 
          562, 2282, 2283, 2280, 2285, 2286, 2287, 2288, 2289, 2290, 2291, 
          2261, 2294, 2295, 2296, 2297, 2298, 2529, 2301, 2302, 2303, 116, 
          2305, 33, 2307, 2306, 2316, 2310, 2311, 2312, 2313, 2314, 2315, 
          2304, 2317, 2318, 2319, 2320, 2321, 2340, 2309, 2324, 2308, 2326, 
          2327, 2323, 2329, 2330, 2331, 2325, 2333, 2322, 2336, 2337, 2338, 
          2339, 2332, 2341, 2343, 117, 2362, 2345, 2347, 2344, 2342, 2350, 
          2351, 2352, 2353, 2354, 2355, 2348, 2357, 2358, 2359, 2360, 2361, 
          2349, 2365, 2364, 2363, 2366, 2367, 2346, 2369, 2370, 2371, 1047, 
          2373, 2372, 2375, 2376, 2377, 2378, 2379, 2380, 2382, 2381, 2384, 
          2383, 2386, 2385, 2388, 2389, 1168, 2391, 2393, 2395, 2396, 2402, 
          2398, 2399, 2400, 2401, 2755, 2403, 2404, 2390, 2405, 2407, 2411, 
          2409, 2410, 2387, 2412, 2413, 2414, 2415, 2408, 2417, 2406, 2419, 
          1743, 2423, 1094, 2425, 2424, 2421, 2428, 2426, 2430, 2431, 2432, 
          2433, 2434, 2435, 2436, 2437, 2429, 2439, 2440, 2441, 2438, 2443, 
          2444, 2445, 2446, 2447, 2448, 2449, 2450, 2451, 2452, 2453, 2454, 
          2455, 2456, 2442, 2459, 2460, 2461, 2462, 2486, 2458, 2465, 2463, 
          2467, 2492, 2469, 2470, 148, 2472, 2464, 2481, 147, 2476, 2479, 
          2478, 2477, 2480, 2475, 2482, 2483, 2485, 2468, 2487, 2488, 2489, 
          2490, 2491, 2473, 2493, 2494, 2495, 121, 2631, 2525, 2500, 2501, 
          2502, 2503, 2504, 2505, 2519, 2507, 2508, 2509, 2510, 2511, 2512, 
          2524, 2514, 2513, 2516, 2517, 2558, 2520, 2521, 1693, 2523, 2496, 
          2522, 2499, 2530, 2528, 2527, 1044, 2532, 2533, 2534, 2531, 2536, 
          2535, 2538, 2539, 2540, 2541, 2542, 2543, 2544, 2545, 2537, 2565, 
          2548, 2549, 2550, 2551, 2552, 2553, 2554, 2555, 2556, 2557, 177, 
          2559, 2560, 2561, 2562, 2563, 2564, 2546, 2566, 2575, 2569, 2570, 
          2571, 2572, 2573, 2574, 2568, 2576, 2577, 2578, 2579, 2580, 2594, 
          2581, 2583, 2567, 2585, 2586, 2582, 2588, 2589, 2590, 2591, 2592, 
          2593, 2584, 2595, 2596, 2597, 2598, 2599, 1696, 2602, 2603, 2617, 
          2605, 2604, 2607, 2608, 2609, 2610, 2611, 2612, 2613, 2614, 2810, 
          2616, 2618, 2619, 2620, 2621, 2622, 2623, 2600, 2625, 2624, 2627, 
          2248, 2630, 2629, 2626, 2615, 2634, 2636, 2635, 2638, 2639, 2637, 
          2641, 2642, 2643, 2644, 2645, 2646, 2633, 2648, 2647, 2650, 2651, 
          2649, 2656, 2654, 2655, 2640, 2657, 2658, 2653, 2660, 3055, 2662, 
          2661, 2664, 2666, 2693, 2668, 2670, 2686, 2667, 2673, 2671, 2675, 
          2672, 2751, 2837, 2677, 2678, 2681, 2682, 2680, 2687, 2685, 2679, 
          2665, 2688, 2676, 2690, 2684, 2689, 2683, 2692, 2674, 2698, 2725, 
          2700, 2701, 2702, 2703, 263, 2705, 2704, 2707, 2708, 2709, 2710, 
          2711, 2712, 2713, 2714, 2699, 2716, 2717, 2718, 2719, 2720, 2721, 
          2722, 2723, 2724, 2715, 2953, 2726, 1190, 2728, 2731, 2733, 2734, 
          2735, 2736, 2727, 2738, 1712, 2740, 2741, 2742, 2746, 2744, 2745, 
          2730, 2747, 2748, 2749, 2739, 3129, 2752, 2743, 2754, 2750, 2757, 
          80, 2758, 2760, 2756, 2762, 2764, 2765, 2766, 2767, 2768, 2769, 
          2770, 2771, 2759, 2773, 2774, 2775, 2776, 2777, 2778, 2779, 2780, 
          2781, 134, 2783, 2786, 2785, 2788, 2789, 2790, 2791, 2792, 2793, 
          2794, 2795, 2796, 2808, 2801, 2799, 2800, 2797, 2802, 2803, 2804, 
          2805, 2807, 2798, 2809, 2787, 2834, 2813, 2812, 2815, 2811, 2817, 
          2820, 2827, 2816, 2821, 2822, 2823, 2824, 2825, 2826, 2818, 2828, 
          2830, 2831, 989, 2833, 2832, 2829, 2890, 2836, 2839, 2840, 2841, 
          2842, 3139, 2844, 2845, 3023, 2843, 65, 3149, 2848, 2851, 1185, 
          2853, 2850, 2855, 2854, 2849, 2856, 1242, 2860, 2862, 2861, 2864, 
          2863, 1794, 2865, 2868, 2867, 2870, 2871, 2935, 2873, 2866, 2875, 
          2874, 2877, 2876, 2879, 2884, 2881, 2882, 2883, 2869, 140, 2888, 
          2889, 2899, 2471, 2892, 2893, 2894, 2895, 2896, 2885, 2898, 2886, 
          2900, 2901, 2902, 2903, 2904, 2897, 2906, 2907, 2909, 2910, 2911, 
          2908, 2913, 2914, 2915, 3147, 2928, 2838, 2919, 2920, 2858, 2922, 
          2917, 2924, 2923, 2921, 2925, 2916, 2929, 2880, 2932, 2931, 2933, 
          2936, 2937, 2938, 2939, 2930, 2942, 2941, 2943, 2944, 2945, 2946, 
          2947, 2940, 2949, 2948, 2952, 982, 2951, 2955, 2956, 2957, 2958, 
          2959, 2927, 2954, 2962, 2963, 2964, 2965, 2966, 2967, 2961, 2969, 
          2970, 2974, 2972, 2975, 2976, 2977, 2978, 2971, 2980, 2981, 2982, 
          2983, 2984, 2985, 2986, 2987, 2988, 2973, 3007, 2990, 2993, 2994, 
          2995, 2996, 2997, 2998, 2999, 727, 2991, 3002, 3003, 3004, 3005, 
          3006, 2992, 3020, 3009, 3011, 3010, 3014, 3015, 3012, 3017, 3018, 
          3019, 3008, 3066, 3022, 3024, 3026, 3039, 3028, 3029, 2891, 3025, 
          3033, 3034, 3035, 3032, 3036, 3030, 3037, 63, 142, 3041, 1520, 
          3045, 3043, 3046, 3048, 3049, 3047, 1728, 3053, 3050, 3052, 3057, 
          3044, 3059, 3093, 3062, 3063, 3060, 3065, 3067, 3064, 3069, 144, 
          3070, 66, 3072, 3075, 3076, 3077, 3078, 3082, 3071, 3081, 3084, 
          3085, 3068, 3087, 3086, 3083, 3089, 3088, 3092, 3021, 3090, 3096, 
          3098, 3095, 3091, 3099, 3100, 3105, 3104, 3101, 3103, 3108, 3109, 
          3110, 3111, 3112, 3126, 3114, 3106, 3117, 3118, 3119, 3123, 3113, 
          3120, 3121, 3116, 3107, 149, 3130, 3127, 3128, 78, 3132, 3134, 
          3135, 3136, 3137, 3138, 669, 3141, 3142, 3143, 3144, 3124, 3140, 
          3148, 3131, 3150, 3146, 3151, 3152, 3157, 3102, 3158, 3154, 79, 
          1025, 275, 155, 908, 67, 2547, 2989, 2878, 2968, 10, 3079, 526, 
          157, 3040, 875, 11, 2979, 1015, 2166, 141, 1286, 2926, 2859, 738, 
          1204, 138, 2697, 2466, 1891, 74, 2587, 2159, 763, 1218, 1900, 1629, 
          1341, 1273, 970, 254, 1568, 2518, 1880, 160, 1769, 2912, 1972, 
          2195, 1897, 635, 2139, 1330, 2905, 2474, 1344, 2089, 2737, 1178, 
          3133, 2300, 1725, 1092, 1573, 1678, 1816, 3000, 867, 2072, 2079, 
          1935, 1724, 1000, 1076, 760, 83, 2427, 1718, 3058, 1435, 24, 1660, 
          1424, 2706, 211, 1311, 1302, 2374, 710, 508, 100, 3038, 
          882};

eta2 = {336, 634, 925, 1202, 1554, 2144, 2392, 2394, 373, 2669, 2695, 
          2732, 2806, 2484, 3013, 3061, 3097, 3156, 768, 136, 809, 1989, 
          1436, 1639, 1247, 492, 817, 1126, 303, 1792, 25, 113, 3031, 1156, 
          2934, 586, 1283, 197, 2422, 3051, 2763};

Do this for any optimal base !

B = Transpose[Transpose[A][[ base ]]];
W = Inverse[B];
cb = c[[ base ]];
Which[eta1=={}
     ,x = W. (b-Transpose[AT[[eta2]]].ub[[eta2]]);
      value=cb.x+c[[eta2]].ub[[eta2]]
     ,eta2=={}
     ,x = W. (b-Transpose[AT[[eta1]]].lb[[eta1]]);
      value=cb.x+c[[eta1]].lb[[eta1]]
     ,True
     ,x = W. (b-Transpose[AT[[eta2]]].ub[[eta2]]-
                Transpose[AT[[eta1]]].lb[[eta1]]);
      value=cb.x+
         c[[eta2]].ub[[eta2]]+c[[eta1]].lb[[eta1]]
      ];
 u = cb . W;
cr = c - u . A;
      Print[N[value]];

Current solution

(blue arcs -> x=1; red arcs -> x=1/2;  othercolors ->  x fractional and not 1/2)

solution=Table[0,{n}];
Do[solution[[base[[i]]]]=x[[i]],{i,m}];
Do[solution[[eta1[[i]]]]=lb[[eta1[[i]]]]
            ,{i,Length[eta1]}];
Do[solution[[eta2[[i]]]]=ub[[eta2[[i]]]]
            ,{i,Length[eta2]}];

solution = Chop[solution];

tour={};
Do[If[solution[[i]]==1,
       AppendTo[tour,arclist[[i]]]],
  {i,na}];
 tour

fractset={};
Do[If[ (solution[[i]]==1/2),
      AppendTo[fractset,arclist[[i]]]],
  {i,na}];
  fractset

fractset2={};
Do[If[ (solution[[i]]!=1/2) && (solution[[i]]!=1) && (solution[[i]]!=0),
      AppendTo[fractset2,arclist[[i]]]],
  {i,na}];
  fractset2

posarcs = 
        Select[Transpose[{Take[solution, na], arclist}],  #[[1]] > 
              0  &];

eee = show[fractset2, 1, 1, "G"];

ddd=show[fractset,1,1,"R"];

ccc=show[tour,2,0,"B"];

Show[eee, ccc, ddd, aaa, AspectRatio -> Automatic, 
        PlotRange -> All];

Cutting

Subtour elimination

(nodeset is the set S such that x(S)>|S|-1)

Manual subset identification

nodeset={24,5,37,46}

addsubtourrow;
reoptimize

Automatic subset identification via randomized min cut

cutsearch[posarcs]

addsubtourrow;
reoptimize

Combs

{handle,teeth} is the comb which must be added

{handle,teeth}={{52,23,61},{{23,70},{52,36},{61,19}}}

addcombrow;
reoptimize

Branching

Local routines

storenewsubproblem[label_] := 
      Module[{}, 
AppendTo[
          subproblems, {label, A, b, c, lb, ub, n, m, base, eta1, 
            eta2}]; 
Print[label, "  is number  ", 
          Length[subproblems]]
]

resumesubproblem[prnum_] := 
      Module[{label}, 
{label, A, b, c, lb, ub, n, m, base, 
            eta1, eta2} = subproblems[[prnum]]; 
AT = 
          Transpose[A]; 
B = 
          Transpose[Transpose[A][[base]]]; 
W = 
          Inverse[B];  
        cb = c[[base]]; 
Which[eta1 == {}, 
          x = W . (b - 
                  Transpose[AT[[eta2]]] . 
                    ub[[eta2]]); 
value = 
            cb . x + 
              c[[eta2]] . 
                ub[[eta2]], 
eta2 == {}, 
          x = W . (b - 
                  Transpose[AT[[eta1]]] . 
                    lb[[eta1]]); 
value = 
            cb . x + 
              c[[eta1]] . lb[[eta1]], 
True,  
          x = W . (b - Transpose[AT[[eta2]]] . ub[[eta2]] - 
                  Transpose[AT[[eta1]]] . 
                    lb[[eta1]]); 
value = 
            cb . x + c[[eta2]] . ub[[eta2]] + 
              c[[eta1]] . lb[[eta1]]]; 
u = 
          cb . W; 
cr = 
          c - u . A; 
Print["resumed problem   ", 
          label, "  with value ", 
          N[value]];
]

updatesubproblem[prn_] := 
      Module[{}, 
label = 
          subproblems[[prn, 
              1]]; 
subproblems[[prn]] = {label, A, 
            b, c, lb, ub, n, m, base, eta1, 
            eta2};
]

\(generatetwins[prn_, a_] := 
      Module[{k, vv, i, 
          j}, 
k = \(Position[\ \(Transpose[
                  searchtree]\)[\([1]\)], prn]\)[\([1, 
              1]\)]; 
{i, j} = a; 
vv = 
          value; 
 (*\(updatesubproblem[
              k];\)*) 
searchtree[\([k, 2]\)] = 
          vv; 
resumesubproblem[
          prn]; 
addbranchrow[{i, j}, 
          0]; 
storenewsubproblem[
          StringJoin[
            ToString[{i, 
                j}], "0"]]; 
searchtree[\([2\ k]\)] = {Length[subproblems], vv}; 
resumesubproblem[
          prn]; 
addbranchrow[{i, j}, 
          1]; 
storenewsubproblem[
          StringJoin[
            ToString[{i, 
                j}], "1"]]; 
searchtree[\([2\ k + 
                1]\)] = {Length[subproblems], 
            vv};
]\)

showsearchtree := 
      Module[{n, maxlev, nodecoord, arcs, truelabels}, 
n = 
          Length[searchtree]; 
maxlev = 
          Floor[Log[2, N[n]]]; 
nodecoord = 
          Table[{0, -Floor[Log[2, N[i]]]}, {i, 
              2^(maxlev + 1) - 1 }]; 
Do[
          nodecoord[[k, 1]] = -2^(maxlev - 1) + 
              0.5 + (k - 2^maxlev), {k, 2^(maxlev), 
            2^(maxlev + 1) - 1}]; 
Do[
          nodecoord[[k, 
                1]] = (nodecoord[[2 k, 1]] + 
                  nodecoord[[2 k + 1, 1]])/2, {k, 2^(maxlev) - 1, 
            1, -1}]; 
arcs = {}; 
Do[
          If[searchtree[[i]] ≠ {0, 0}  &&  
              searchtree[[Floor[ i/2]]] ≠ {0, 
                  0}, 
   AppendTo[
              arcs, {Floor[ i/2],  i}]] , {i, n, 
            2, -1}]; 
truenodes = {}; 
        bounds = {}; 
truelabels = {}; 
        Do[If[searchtree[[i]] ≠ {0, 
                0}, 
                                         AppendTo[truenodes, 
              nodecoord[[i]]]; 
                                         AppendTo[
              truelabels, 
              searchtree[[i, 
                  1]]]; 
                                         AppendTo[bounds, 
              searchtree[[i, 2]]];], {i, n}]; 
Show[
          Graphics[{Map[Line, 
                Map[ Map[ nodecoord[[#]]  &, #] & , arcs]], 
              RGBColor[1, 1, 1], 
              Map[Disk[#,  .2] &, truenodes], 
 (* 
                RGBColor[0, 0, 0], Map[Circle[#,  .2] &, truenodes], *) 
                RGBColor[1, 0, 0],  
MapThread[
                Text, {Map[ToString, truelabels], truenodes}], 
              RGBColor[0, 0, 1], 
MapThread[
                Text, {Map[ToString, bounds], 
                  Map[# + {0,  .4} &, truenodes]}]}], 
          PlotRange -> All];
]

initialization

write first branching arc !

branchingarc = {52, 23};

searchtree = Table[{0, 0}, {65}]; 
    searchtree[[1]] = {1, value}

subproblems = {}; storenewsubproblem["1"];

problemtoprocess = 1

generatetwins[problemtoprocess, branchingarc]

showsearchtree

branch-and-cut computation

select problem to solve

problemtosolve = 2

resumesubproblem[problemtosolve]

reoptimize

See solution

solution=Table[0,{n}];
Do[solution[[base[[i]]]]=x[[i]],{i,m}];
Do[solution[[eta1[[i]]]]=lb[[eta1[[i]]]]
            ,{i,Length[eta1]}];
Do[solution[[eta2[[i]]]]=ub[[eta2[[i]]]]
            ,{i,Length[eta2]}];

solution = Chop[solution];

tour={};
Do[If[solution[[i]]==1,
       AppendTo[tour,arclist[[i]]]],
  {i,na}];
 tour

fractset={};
Do[If[ (solution[[i]]==1/2),
      AppendTo[fractset,arclist[[i]]]],
  {i,na}];
  fractset

fractset2={};
Do[If[ (solution[[i]]!=1/2) && (solution[[i]]!=1) && (solution[[i]]!=0),
      AppendTo[fractset2,arclist[[i]]]],
  {i,na}];
  fractset2

posarcs = 
        Select[Transpose[{Take[solution, na], arclist}],  #[[1]] > 
              0  &];

eee = show[fractset2, 1, 1, "G"];

ddd=show[fractset,1,1,"R"];

ccc=show[tour,2,0,"B"];

Show[eee, ccc, ddd, aaa, AspectRatio -> Automatic, 
        PlotRange -> All];

possibly add cuts

cutsearch[posarcs]

addsubtourrow;
reoptimize

if optimal or fathomed do this NOW

searchtree[[Position[ Transpose[searchtree][[1]], 
              problemtosolve][[1, 1]], 2]] = 
      Ceiling[value]

showsearchtree

if neither  optimal nor fathomed select NOW arc to branch

branchingarc = {71, 78};

problemtoprocess = problemtosolve

generatetwins[problemtoprocess, branchingarc]

showsearchtree

Drawings

Italia

ESEMPIO OTT

Istanza

Al  nodo  radice

Show[eee, ccc, ddd, aaa, AspectRatio -> Automatic, 
      PlotRange -> 1.1 rangeplot]

Dopo subtour

Show[eee, ccc, ddd, aaa, AspectRatio -> Automatic, 
      PlotRange -> 1.1 rangeplot]

Show[eee, ccc, ddd, aaa, AspectRatio -> Automatic, 
      PlotRange -> 1.1 rangeplot]

Dopo comb

Show[eee, ccc, ddd, aaa, AspectRatio -> Automatic, 
      PlotRange -> 1.1 rangeplot]

Dopo branching con 10-15-->0  v=382

Show[eee, ccc, ddd, aaa, AspectRatio -> Automatic, 
      PlotRange -> 1.1 rangeplot]

Dopo branching con 10-15-->1  v=385

Show[eee, ccc, ddd, aaa, AspectRatio -> Automatic, 
      PlotRange -> 1.1 rangeplot]

subtours

{{12, 8, 5}, {12, 8, 5, 11, 4, 10, 13}}

combs

{{{15, 3, 10}, {{13, 10}, {3, 1}, {2, 15}}}, 
{{2, 
          14, 5}, {{14, 6}, {5, 12}, {2, 15}}}, 
{{4, 10, 
          13, 3, 15}, {{3, 1}, {4, 11}, {2, 15}}}, 
{{3, 1, 
          10}, {{3, 15}, {10, 13}, {1, 9}}}}