finding Hamiltonian Path in TSP Topic is solved

Problems with syntax of GAMS
Post Reply
Parisa
User
User
Posts: 14
Joined: 5 years ago

finding Hamiltonian Path in TSP

Post by Parisa »

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.

Code: Select all

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;
                                         );
                                 );
                         );
                 );
         );
);
);
);
User avatar
bussieck
Moderator
Moderator
Posts: 1033
Joined: 7 years ago

Re: finding Hamiltonian Path in TSP

Post by bussieck »

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/ ... ml#gamslib and search for tsp.

-Michael
Parisa
User
User
Posts: 14
Joined: 5 years ago

Re: finding Hamiltonian Path in TSP

Post by Parisa »

I don't want to eliminate this answer, just want to check it's validity.
User avatar
bussieck
Moderator
Moderator
Posts: 1033
Joined: 7 years ago

Re: finding Hamiltonian Path in TSP

Post by bussieck »

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
Parisa
User
User
Posts: 14
Joined: 5 years ago

Re: finding Hamiltonian Path in TSP

Post by Parisa »

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