TSP - Indexing with string members in the set

Support
1

Hello,

I am trying to solve the traveling salesman problem and I ran into the problem how to set the subtour eliminating constraints in case the set CITY contains string memebrs like Velvary. It is the depot and I need to specify the constraints for j>1 (please see the example):

subject to cycle{i in CITY, j in CITY: j >1}: u[i]+1-(N-1)*(1-x[i,j])<=u[j];

It works if there are numbers in the set CITY. Of course, I can write the following:

subject to cycle{i in CITY, j in CITY: j != ‘CITY-NAME’}: u[i]+1-(N-1)*(1-x[i,j])<= u[j];

But it is not general expression (if the set CITY is changed, I have to change the model as well). I need sth like

j in CITY: index(CITY,j)>1

Please can you help me? I know that there is FIRST function, but it does not work with unordered sets…

If you need more explanations, please let me know.

Thank you,
Ondřej Šafka

2

You can take your choice of two approaches here.

  1. Define CITY as an ordered set:
set CITY ordered;

In your data, put Velvary first in the list of cities. Then you can write the constraint as:

subject to cycle {i in CITY, j in CITY: j != first(CITY)}: 
   u[i]+1-(N-1)*(1-x[i,j])<=u[j];
  1. Define a parameter that specifies the city that is the depot:
set CITY;
param Depot symbolic in CITY;

(The keyword “symbolic” indicates that this param has a string value rather than a numerical value.) Specify CITY and Depot in your data:

set CITY := Velvary A B C ;
param Depot := Velvary ;

Then you can write the constraint as:

subject to cycle {i in CITY, j in CITY: j != Depot}: 
   u[i]+1-(N-1)*(1-x[i,j])<=u[j];
3

Thank you, it is what we were looking for:)