TSP - Indexing with string members in the set

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

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];

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