In this model we formulate the subtour elimination restrictions by using an intuitive approach. However, as you will see, this turns out rather difficult to implement in GAMS. Also the number of constraints added is very large: power(2,n)-2
The two formulations we implemented are:
sum((i,j)$(S(i) and S(j)), x(i,j)) <= |S|-1
and
sum((i,j)$(S(i) and T(j)), x(i,j)) >= 1
S is the set of all subsets of N={1,2,..n} (such a set is called the powerset of N) except the empty set and N itself. T is the complement of S.
Constructing the powerset in GAMS is not a trivial task. We have used a "recursive" scheme.
We use the same 6 city problem as in tsp1 and tsp2.