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