Subtour elimination constraints of a symmetric Travelling Salesman in IBM Cplex

Question

There is a sample code for travelling salesman problem in IBM Cplex. It defined the subtour elimination constraint as this:

   forall (s in subtours)
   sum (i in Cities : s.subtour[i] != 0)
      x[<minl(i, s.subtour[i]), maxl(i, s.subtour[i])>]
       <= s.size-1;

Can someone help me with the equivalent mathematical formulation of this code lines?

Answer 1

Can someone help me with the equivalent mathematical formulation of this code lines?

Where:

xij = 1 if the the salesman traverses the link from city i to city j, 0 otherwise
S = a subtour, which is a subset of cities (which in turn is an ordered set).
i, j = two cities that belong to the subtour

The formulation is taken from here and refers to the symmetric travelling salesman problem (the cost of going from i to j is the same as the cost of going from j to i). As such, variables xij are defined only for i < j.

I am not an OPL expect, but would explain the code as follows:

subtours is a tuple, which is like a C/C++ struct:

tuple Subtour { int size; int subtour[Cities]; }
{Subtour} subtours = ...;

I understand that subtours is defined as of type Subtour, which holds an array, defined over the cities, but of size pointed by the size variable (because not all cities may be part of a given subtour).

forall (s in subtours) is self-explanatory, corresponds to the for each part of the formulation.

sum (i in Cities : s.subtour[i] != 0)

I saw in the source code that subtour is an array that for each city i, subtour[i] is the successor of i. So, given a subtour, this line sums all the cities that have a successor city.

x[<minl(i, s.subtour[i]), maxl(i, s.subtour[i])>] <= s.size-1;

This refers to the variable xij, but takes care of the fact that i < j, because in a symmetric TSP it is not necessary to define variables for both i < j and j < i.

The subtour elimination constraints are added dynamically in the source code (and in most implementations, as their number is exponential, 2^(n-1 + n - 2), so O(2^n)).

In logic terms, the constraints say that any given set of cities should be connected and no subtours are allowed.

I hope this helps!