$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: http://www.gams.com/modlib/adddocs/tsp3doc.htm 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;