finding Hamiltonian Path in TSP Topic is solved

Problems with syntax of GAMS
Post Reply
Parisa
User
User
Posts: 3
Joined: 8 months ago

finding Hamiltonian Path in TSP

Post by Parisa » 7 months ago

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: 340
Joined: 2 years ago

Re: finding Hamiltonian Path in TSP

Post by bussieck » 7 months ago

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: 3
Joined: 8 months ago

Re: finding Hamiltonian Path in TSP

Post by Parisa » 7 months ago

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

User avatar
bussieck
Moderator
Moderator
Posts: 340
Joined: 2 years ago

Re: finding Hamiltonian Path in TSP

Post by bussieck » 7 months ago

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: 3
Joined: 8 months ago

Re: finding Hamiltonian Path in TSP

Post by Parisa » 7 months ago

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

Post Reply