Description

This is the fifth problem in a series of traveling salesman
problems. Here we use a compact formulation that ensures no subtours
due to Miller, Tucker and Zemlin.

Moreover, we use a dynamic subtour elimination using even stronger
cuts than in the previous models. Also the GAMS programming is more
compact than in the previous examples.

Reference

• Miller, C E, Tucker, A W, and Zemlin, R A, Integer Programming Formulation of Traveling Salesman Problems. J. ACM 7, 4 (1960), 326-329.

Large Model of Type : MIP

Category : GAMS Model library

Main file : tsp5.gms   includes :  br17.inc

$title Traveling Salesman Problem - Five (TSP5,SEQ=345)

$onText
This is the fifth problem in a series of traveling salesman
problems. Here we use a compact formulation that ensures no subtours
due to Miller, Tucker and Zemlin.

Moreover, we use a dynamic subtour elimination using even stronger
cuts than in the previous models. Also the GAMS programming is more
compact than in the previous examples.


Miller, C E, Tucker, A W, and Zemlin, R A, Integer Programming
Formulation of Traveling Salesman Problems. J. ACM 7, 4 (1960),
326-329.

Keywords: mixed integer linear programming, traveling salesman problem, Miller-
          Tucker-Zemlin subtour elimination, iterative subtour elimination
$offText

$include br17.inc

Set i(ii) / i1*i17 /;

* Build compact TSP model
Positive Variable p(ii) 'position in tour';

Equations defMTZ(ii,jj) 'Miller, Tucker and Zemlin subtour elimination';

defMTZ(i,j).. p(i) - p(j) =l= card(j) - card(j)*x(i,j) - 1 + card(j)$(ord(j) = 1);

Model MTZ / all /;

p.fx(j)$(ord(j) = 1) = 0;
p.up(j) = card(j) - 1;

option optCr = 0, resLim = 30;

solve MTZ min z using mip;

* Dynamic subtour elimination
Set
   ste         'possible subtour elimination cuts' / c1*c1000 /
   a(ste)      'active cuts'
   tour(ii,jj) 'possible subtour'
   n(jj)       'nodes visited by subtour';

Parameter
   proceed       'indicator to continue to eliminate subtours' / 1 /
   cc(ste,ii,jj) 'cut coefficients'
   rhs(ste)      'right hand side of cut';

Equation defste(ste) 'subtour elimination cut';

defste(a).. sum((i,j), cc(a,i,j)*x(i,j)) =l= rhs(a);

Model DSE / rowsum, colsum, objective, defste /;

a(ste)    = no;
cc(a,i,j) =  0;
rhs(a)    =  0;

option limRow = 0, limCol = 0, solPrint = silent, solveLink = 5;

loop(ste$proceed,
   if(proceed = 1,
      solve DSE min z using mip;
      abort$(DSE.modelStat <> %modelStat.optimal%) 'problems with MIP solver';
      x.l(i,j) = round(x.l(i,j));
      proceed = 2;
   );

*  Check for subtours
   tour(i,j) = no;
   n(j)      = no;
   loop((i,j)$(card(n) = 0 and x.l(i,j)), n(i) = yes);

*  Found all subtours, resolve with new cuts
   if(card(n) = 0,
      proceed = 1;
   else
*  Construct a single subtour and remove it by setting x.l=0 for its edges
      while(sum((n,j), x.l(n,j)),
         loop((i,j)$(n(i) and x.l(i,j)),
            tour(i,j) = yes;
            x.l(i,j)  =   0;
            n(j)      = yes;
         );
      );
      if(card(n) < card(j),
         a(ste)   = 1;
         rhs(ste) = card(n) - 1;
         cc(ste,i,j)$(n(i) and n(j)) = 1;
      else
         proceed = 0;
      );
   );
);
if(proceed = 0,
   display 'Optimal tour found', tour;
else
   abort 'Out of subtour cuts, enlarge set ste';
);