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)
$eolcom //
$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

$Offtext

$include br17.inc

* first select a small subset
set i(ii) / i1*i6 /;

* 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

sets n subtour id  / n1*n500/  //  maximum of 1000 subsets
     nn(n), nnn(n), curn(n)
     si(n,i)     subset
     sicomp(n,i) subsets complements;

* 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;

* exclude empty rows like
*      i1   i2   i3
*  n2  no   no   no
* and "full" rows like:
*      i1   i2   i3
*  n7  yes  yes  yes
*
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;


equations  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/;
model subt2 /objective, rowsum, colsum, se2/;

solve subt1 using mip minimizing z;
display x.l

solve subt2 using mip minimizing z
display x.l;