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.
```

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:

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;
``````
GAMS Development Corp.
GAMS Software GmbH

General Information and Sales
U.S. (+1) 202 342-0180
Europe: (+49) 221 949-9170