AMPL Travelling salesman problem

[John Lotus]

Hi to everyone, 

i'm trying to solving this problem:

I have the position of n city, each city has the same distances. what I have to do is go through all the cities and return to the starting point. 

This problem is a travelling salesman problem and my question is, is possible to resolve it?

Righ now i have created this program:

TSP.DAT:

### SET###

set CITY1;

set CITY2;

### PARAM###

param dist_city{ CITY1  ,  CITY2} >= 0 integer;

param pos_city{ CITY1  ,  CITY2} >= 0 integer;

param city_tot = 10;

### VAR ###

var x{i in  CITY1  , j in  CITY2} >= integer;

### CONSTRAINT ###

subject to sum_city {i in  CITY1  , j in  CITY2}: b[i,j] = city_tot;

### OBJ ###

minimize final_dist: sum{i in  CITY1  , j in  CITY2} dist_city[i,j];

TSP.DAT:

### VALUE OF SET ###

set  CITY1  := 1 2 3 4 5 6;

set  CITY2  := 1 2 3 4;

### VALUE FOR PARAM ###

 param pos_city:

1  2  3  4  5  6 :=

1 0  1  1  1  1  0 

2 0  1  1  1  1  0

3 0  1  1  1  1  0

4 0  0  0  0  0  0 ;

  param dis_city:

1  2  3  4  5  6 :=

1 0  1  1  1  1  0 

2 0  1  1  1  1  0

3 0  1  1  1  1  0

4 0  0  0  0  0  0 ;

TSP.RUN:

reset;

option solver gurobi;

model TSP.mod;

data TSP.dat;

solve;

display x;

display  final_dist  ;

Let me explain what i have done:

-starting form TSP.DAT, i've thought of creating a matrix pos_city where the city are (are indicated with 1, with 0 no city) and the matrix dist_city (this 2 matrix are identical).

-meanwhile TSP.MOD, i considered the constraint where i want to pass in every single city.

But i think that my view is to simple and not accurate. 

What do you think? Is a solvable problem?

Thak you for your time, 

Jhon Lotus.

[AMPL Google Group]

The model you have written cannot possibly solve the TSP, because the variables x do not appear in the objective function or in the constraints. Also the standard TSP has only one set of cities.

For a discussion of the correct formulation using so-called MTZ constraints, see https://groups.google.com/g/ampl/c/sijPeX1_rE0/m/nxqUFYdMCgAJ in our user forum. Also there is a link to a subtour-elimination formulation of the TSP in the AMPL Frequently Asked Questions, under "How can I get AMPL to index over the “power set” consisting of all subsets of a set?"

--
Robert Fourer
am...@googlegroups.com

{#HS:1696921977-107171#}

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/999da534-e05c-4dfb-802e-f4ada1407496n%40googlegroups.com.

[John Lotus]

Thank you so much for your prompt reply, 

yes the variables x do not appear in the objective function or in the constraints, this is because my doubt is:

is it possible to optimize a TSP problem when all the nodes / cities have the same weight and the same distance? 

wouldn't the problem give infinite solutions?

Thank you very much for your time and patience, i will also read the link that you reccomended

[AMPL Google Group]

If the distance between any two nodes is the same, then every tour of the nodes will have the same total distance traveled. Thus every tour will be optimal.

However, I am not sure if this is what you mean when you say that all nodes have the same distance. Also you say that all nodes have the same weight, but I am not sure how you define "weight" or how weight is important for the TSP.

--
Robert Fourer
am...@googlegroups.com

{#HS:1696921977-107171#}

On Tue, Nov 16, 2021 at 9:26 AM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Thank you so much for your prompt reply,
yes the variables x do not appear in the objective function or in the constraints, this is because my doubt is:
is it possible to optimize a TSP problem when all the nodes / cities have the same weight and the same distance?
wouldn't the problem give infinite solutions?

Thank you very much for your time and patience, i will also read the link that you reccomended

On Mon, Nov 15, 2021 at 10:38 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

The model you have written cannot possibly solve the TSP, because the variables x do not appear in the objective function or in the constraints. Also the standard TSP has only one set of cities.

For a discussion of the correct formulation using so-called MTZ constraints, see https://groups.google.com/g/ampl/c/sijPeX1_rE0/m/nxqUFYdMCgAJ in our user forum. Also there is a link to a subtour-elimination formulation of the TSP in the AMPL Frequently Asked Questions, under "How can I get AMPL to index over the “power set” consisting of all subsets of a set?"

--
Robert Fourer
am...@googlegroups.com