Help in Modeling travelling salesman problem.

Problems with modeling
Post Reply
thegorila78
User
User
Posts: 2
Joined: 5 years ago

Help in Modeling travelling salesman problem.

Post by thegorila78 »

I am having trouble modeling the last constraint for this TSP model. I have the first 3 constraints modeled properly but the last one I can't figure out how to model in GAMS. I attached my code and a screenshot of the constraints. Specifically the last one requires me to keep track of a subset in GAMS and I am confused about how to do that. Any help would be appreciated.
Attachments
Screen Shot 2019-03-12 at 8.44.22 PM.png
hw6-1.gms
Travelling salesman problem
(1.12 KiB) Downloaded 348 times
User avatar
bussieck
Moderator
Moderator
Posts: 1033
Joined: 7 years ago

Re: Help in Modeling travelling salesman problem.

Post by bussieck »

Since there are exponentially many subtours (subsets of {2..n}) you would not do this explicitly. For small n you would use the compact MTZ formulation (see https://www.gams.com/latest/gamslib_ml/ ... _tsp5.html). For larger instances you should generate the subtour constraints that are needed using an iterative approach, see tsp1*tsp4 in the GAMS Model Library (https://www.gams.com/latest/gamslib_ml/ ... _tsp1.html). For very large (and pure) TSP problems you would use a special purpose solver (not part of GAMS) like Concorde (http://www.math.uwaterloo.ca/tsp/concorde.html).

-Michael
thegorila78
User
User
Posts: 2
Joined: 5 years ago

Re: Help in Modeling travelling salesman problem.

Post by thegorila78 »

bussieck wrote: 5 years ago Since there are exponentially many subtours (subsets of {2..n}) you would not do this explicitly. For small n you would use the compact MTZ formulation (see https://www.gams.com/latest/gamslib_ml/ ... _tsp5.html). For larger instances you should generate the subtour constraints that are needed using an iterative approach, see tsp1*tsp4 in the GAMS Model Library (https://www.gams.com/latest/gamslib_ml/ ... _tsp1.html). For very large (and pure) TSP problems you would use a special purpose solver (not part of GAMS) like Concorde (http://www.math.uwaterloo.ca/tsp/concorde.html).

-Michael
How would I do this the naive way? Like by running the model over and over again until I got a solution.

Thanks for the response!
User avatar
bussieck
Moderator
Moderator
Posts: 1033
Joined: 7 years ago

Re: Help in Modeling travelling salesman problem.

Post by bussieck »

Look at this post: viewtopic.php?f=9&t=10428&p=24102. Here all subsets of a set are generated via the powerSetRight operator. That should help you doing it in the naive way.

-Michael
devin29
User
User
Posts: 1
Joined: 4 years ago

Re: Help in Modeling travelling salesman problem.

Post by devin29 »

Hello there,
thegorila78 wrote: 5 years ago I am having trouble modeling the last constraint for this TSP model. I have the first 3 constraints modeled properly but the last one I can't figure out how to model in GAMS. I attached my code and a screenshot of the constraints. Specifically the last one requires me to keep track of a subset in GAMS and I am confused about how to do that. Any help would be appreciated.
The Mathematical Model of Traveling Salesman Problem with Alternative Pick up and Delivery nodes. The original single/multi automated guided vehicle (AGV) scheduling problem with a specific pick up and delivery node can be formulated and solved as single/multi traveling salesman problem (TSP/MTSP).
Post Reply