[AMPL 24472] subtour elimination constraints

Hi to everyone
I am trying to solve a Travelling Salesman Problem using the Matlab API of AMPL. I imposed the subtour elimination constraints through the following formulation

ampl.eval(‘subtour_elimination {(i,j) in E: i >= 2 && i != j && j!=1}: u[i] + x[i,j] <= u[j] + (n - 1) * (1 - x[i,j]);’);
ampl.eval(‘subtour_elimination_2_a {k in K: k = 1}: u[k] = 0;’);
ampl.eval(‘subtour_elimination_2_b {k in K: k >= 1}: u[k] <= n-1;’);

The problem is that it doesn’t seem to work, as in the final solution I still have 5/6 subtours. Does anyone have any suggestion on how to improve this formulation ? To give an idea of the problem size, I have a graph with 1200 nodes and 2600 edges, and the solver is CPLEX.

Thank you in advance

Pietro

Are you trying to write the Miller-Tucker-Zemlin subtour elimination constraints, as described for example on this page?

https://phabi.ch/2021/09/19/tsp-subtour-elimination-by-miller-tucker-zemlin-constraint/

It appears that your AMPL constraints are not quite the same as the ones in this example. Most seriously, it appears that your constraints subtour_elimination_2_a and subtour_elimination_2_b are satisfied by setting u[k] = 0 for all k in K, and as a result they do not prevent subtours. To see how this should be fixed, compare your constraints to the ones in the example.

Dear Robert

Thank you so much for your answer. In fact I already tried a formulation like the one which is reported in the link, but it didn’t work. I implemented it with these commands:

ampl.eval(‘subtour_elimination {(i,j) in E: i != 1 && j!=1}: u[i]- u[j] + 1 <= (n - 1) * (1 - x[i,j]);’);
ampl.eval(‘subtour_elimination_2_a {k in K: k = 1}: u[k] = 1;’);
ampl.eval(‘subtour_elimination_2_b {k in K: k != 1}: u[k] <= n;’);
ampl.eval(‘subtour_elimination_2_c {k in K: k != 1}: u[k] >= 2;’);

where E is the set of edges and K is the set of nodes. Do you have any idea of what I am doing wrong ?

Thank you again

Pietro Silvestri

Indeed, there seems to be an error in the formulation given on that webpage. You can see that something looks wrong with the “subtour_elimination” constraints, because u[1] does not appear in any of them. I believe the indexing should be

{(i,j) in E: j != 1}

I tried also with this indexing but it is still not working

Pietro Silvestri

You could try using AMPL’s tools to debug your formulation. For example, if the solver reports “optimal solution” but “display x;” shows that x[5,6] = x[6,7] = x[7,5], then you have a subtour from 5 to 6 to 7 to 5. You can use AMPL’s “expand” command to look at the constraints that are supposed to eliminate that subtour:

expand subtour_elimination[5,6];
expand subtour_elimination[6,7];
expand subtour_elimination[7,5];

Then you can ask yourself what’s wrong with these constraints that is allowing the subtour to exist in the solution.

There are other constraints besides the subtour elimination ones that could be in error, however, and the solver might be reporting “infeasible” instead of “optimal”. So instead of debugging you could look at the formulations that were given in this earlier posting:

https://groups.google.com/g/ampl/c/sijPeX1_rE0/m/hbddy0aWDAAJ

Thank you for your answer. Finally, it came out that this formulation can work for small size problems (around 50 stops), whereas for bigger problems I had to set up a recursive formulation, which is working fine. Thank you again.

Pietro Silvestri