tsp5.gms : TSP solution with Miller et al subtour elimination

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';
);