eliminating short-cycles in TSP

[kiko]

On the AMPL web-page there is an example for programming the TSP as an
integer linear program (http://www.ampl.com/FAQ/tsp.mod). To eliminate
short cycles there is a special subject to condition.
It works very well, but I still didn't understand how it works.
Can anybody explain the exact functionality of the short-cycle
elimination used in the example?

Thank you for any help in advance

Niko

[Robert Fourer]

The following statements in tsp.mod define an indexed collection of sets
POW[k] such that, for each k from 1 to 2**n-2, POW[k] is one of the subsets
of the node set S:

set S ordered;
param n := card {S};
set SS := 0 .. (2**n - 1);
set POW {k in SS} := {i in S: (k div 2**(ord(i)-1)) mod 2 = 1};

The constraints of interest define one "subtour elimination" condition for
each subset POW[k] of S:

subj to SubtourElim {k in SS diff {0,2**n-1}}:
sum {i in POW[k], j in S diff POW[k]: (i,j) in LINKS} X[i,j] +
sum {i in POW[k], j in S diff POW[k]: (j,i) in LINKS} X[j,i] >= 2;

These constraints say that the number of arcs in the solution that connect a
node in POW[k] to a node *not* in POW[k] must be at least 2. This rules out
a solution that has a subtour of nodes that lie entirely within POW[k].

Of course the number of constraints, being on the order of the number of
subsets or 2**n, grows exponentially with the number n of nodes. Hence this
formulation is practical only for small examples. For larger cases it's
necessary to generate subtour elimination constraints only as they are
needed.

Bob Fourer
4...@ampl.com