finding Hamiltonian Path in TSP

GAMS
1

Hello,
I have written piece of Code for controlling that whether the Answer is a complete Cycle(Hamiltonian Cycle) or it is just a Sub-tour in Travelling Salesman Problem. Suppose that we have an Answer which starts from City"1", if we have such a Cycle then “flag=1”.
Any Help will be appreciated.

loop(i$(ord(i)<>1),
         if(x.l('1',i)=1,
                 loop((j,v)$((ord(i)<>ord(j)) and (ord(j)<>ord(v)) and ord(i)<>ord(v)),
                         if(x.l(i,j)=1 and x.l(j,v)=1,
                                 loop(y$(ord(y)<>1),
                                         if(x.l(y,'1')=1,
                                                 flag=1;
                                         );
                                 );
                         );
                 );
         );
);
);
);
2

Have you looked at the code of the TSP examples in GAMS Model Library? Some of them implement subtour elimination cuts and therefore need to answer exactly your question. See https://www.gams.com/latest/gamslib_ml/libhtml/index.html#gamslib and search for tsp.

-Michael

3

I don’t want to eliminate this answer, just want to check it’s validity.

4

Same thing. The algorithm (for adding subtour cuts) terminates if there is no subtour. So just try to understand the algorithm to find the subtours.

-Michael

5

Thank you for that Link, That gave me other Ideas for coding.