tsp3.gms : Traveling Salesman Problem - Three

**Description**

This is the third problem in a series of traveling salesman problems. The formulation uses a subtour elimination based on logic to find all subtours first, and then add appropriate eliminations constraints.

**References**

- Lawler, E L, Lenstra, J K, Rinnoy Kan, A H G, and Shmoys, D B, Eds, The Traveling Salesman Problem, A Guided Tour of Combinatorial Optimization. Wiley, 1985.
- Kalvelagen, E, Model Building with GAMS. forthcoming

**Small Model of Type :** MIP

**Category :** GAMS Model library

**Main file :** tsp3.gms **includes :** br17.inc

```
$title Traveling Salesman Problem - Three (TSP3,SEQ=179)
$onText
This is the third problem in a series of traveling salesman
problems. The formulation uses a subtour elimination based
on logic to find all subtours first, and then add appropriate
eliminations constraints.
Kalvelagen, E, Model Building with GAMS. forthcoming
de Wetering, A V, private communication.
Lawler, E L, Lenstra, J K, Kan, A H G R, and Shmoys, D B, Eds, The
Traveling Salesman Problem, A Guided Tour of Combinatorial
Optimization. Wiley, 1985.
Additional information can be found at:
http://www.gams.com/modlib/adddocs/tsp3doc.htm
Keywords: mixed integer linear programming, traveling salesman problem, subtour
elimination
$offText
$eolCom //
$include br17.inc
* first select a small subset
Set i(ii) / i1*i6 /;
$onText
This code is tricky and the generation of all
subsets is explained by example below:
First we take one element
n1 yes
n2 no
Then for i = i2 we have
n1 yes no
n2 no no
n3 yes yes copy of n1 plus adding i2=yes
n4 no tes copy of n2 plus adding i2=yes
Then for i = i3 we have
n1 yes no no
n2 no no no
n3 yes yes no
n4 no yes no
n5 yes no yes
n6 no no yes
n7 yes yes yes
n8 no yes yes
$offText
Set
n 'subtour id' / n1*n500 / // maximum of 1000 subsets
si(n,i) 'subset'
sicomp(n,i) 'subsets complements'
nn(n)
nnn(n)
curn(n);
* initialize tree
si('n1','i1') = yes;
si('n2','i1') = no;
curn('n2') = yes;
nnn('n1') = yes;
nnn('n2') = yes;
loop(i$(ord(i) > 1),
// make a copy of all previously generated sets
// one copy is to include i, the other one not.
nn(n) = nnn(n);
loop(nn,
curn(n) = curn(n-1);
nnn(curn) = yes;
si(curn, j) = si(nn,j); // copy old one
si(curn, i) = yes;
);
);
sicomp(nnn,i) = not si(nnn,i);
display si, sicomp;
$onText
exclude empty rows like
i1 i2 i3
n2 no no no
and "full" rows like:
i1 i2 i3
n7 yes yes yes
$offText
Set n1(n) 'simplified set of subtours';
n1(nnn) = yes;
n1(nnn)$(sum(i$si(nnn,i),1) = 0) = no;
n1(nnn)$(sum(i$si(nnn,i),1) = card(i)) = no;
Equation
se1(n) 'subtour elimination 1'
se2(n) 'subtour elimination 2';
se1(n1).. sum(i$si(n1,i), sum(j$si(n1,j), x(i,j))) =l= sum(si(n1,i),1) - 1;
se2(n1).. sum(si(n1,i), sum(sicomp(n1,j), x(i,j))) =g= 1;
Model
subt1 / objective, rowsum, colsum, se1 /
subt2 / objective, rowsum, colsum, se2 /;
solve subt1 using mip minimizing z;
display x.l
solve subt2 using mip minimizing z;
display x.l;
```