Description

This is the first problem in a series of traveling salesman
problems. In this problem we first solve an assignment
problem as a relaxation of the TSP. Subtours of this solution
are detected and printed. The subtours are then eliminated via
cuts (constraints that eliminate solution with subtours).

Note: we deal here with an unsymmetric TSP. If symmetric
      one can add 2 cuts in each cycle: forward and
      backward.

Additional information can be found at:

http://www.gams.com/modlib/adddocs/tsp1doc.htm

Small Model of Type : MIP

Category : GAMS Model library

Main file : tsp1.gms   includes :  br17.inc

$title Traveling Salesman Problem - One (TSP1,SEQ=177)

$onText
This is the first problem in a series of traveling salesman
problems. In this problem we first solve an assignment
problem as a relaxation of the TSP. Subtours of this solution
are detected and printed. The subtours are then eliminated via
cuts (constraints that eliminate solution with subtours).

Note: we deal here with an unsymmetric TSP. If symmetric
      one can add 2 cuts in each cycle: forward and
      backward.

Additional information can be found at:

http://www.gams.com/modlib/adddocs/tsp1doc.htm


Kalvelagen, E, Model Building with GAMS. forthcoming

de Wetering, A V, private communication.

Keywords: mixed integer linear programming, traveling salesman problem, iterative
          subtour elimination, cut generation
$offText

$eolCom //

$include br17.inc

* For this simple algorithm the problem is too difficult
* so we consider only the first 6 cities.
Set i(ii) / i1*i6 /;

* options. Make sure MIP solver finds global optima.
option optCr = 0;

Model assign / objective, rowsum, colsum /;

solve assign using mip minimizing z;

* find and display tours
Set t 'tours' / t1*t17 /;
abort$(card(t) < card(i)) "Set t is possibly too small";

Parameter tour(i,j,t) 'subtours';

Singleton Set
   from(i) 'contains always one element: the from city'
   next(j) 'contains always one element: the to city'
   tt(t)   'contains always one element: the current subtour';

Set visited(i) 'flag whether a city is already visited';

* initialize
from(i)$(ord(i) = 1) = yes;    // turn first element on
tt(t)$(  ord(t) = 1) = yes;    // turn first element on

loop(i,
   next(j)$(x.l(from,j) > 0.5) = yes;    // check x.l(from,j) = 1 would be dangerous
   tour(from,next,tt) = yes;             // store in table
   visited(from) = yes;                  // mark city 'from' as visited
   from(j) = next(j);
   if(sum(visited(next),1) > 0,          // if already visited...
      tt(t) = tt(t-1);
      loop(k$(not visited(k)),           // find starting point of new subtour
         from(k) = yes;
      );
   );
);

display tour;

* subtour elimination by adding cuts
* the logic to detect if there are subtours is similar
* to the code above
Set cc / c1*c100 /;  // we allow up to 100 cuts

Alias (cc,ccc);

Set
   curcut(cc)  'current cut always one element'
   allcuts(cc) 'total cuts';

Parameter cutcoeff(cc, i, j);

Equation cut(cc) 'dynamic cuts';

cut(allcuts).. sum((i,j), cutcoeff(allcuts,i,j)*x(i,j)) =l= card(i) - 1;

Model tspcut / objective, rowsum, colsum, cut /;

curcut(cc)$(ord(cc) = 1) = yes;

Scalar ok;

loop(ccc,
   from(i)    = ord(i) = 1;      // initialize from to first city
   visited(i) = no;
   ok = 1;
   loop(i$((ord(i) < card(i)) and ok),       // last city can be ignored
      next(j) = x.l(from,j) > 0.5;           // find next city
      visited(from) = yes;
      from(j)       = next(j);
      ok$sum(visited(next),1) = 0;           // we have detected a subtour
   );
   break$(ok = 1); // done: no subtours

   // introduce cut
   cutcoeff(curcut, i, j)$(x.l(i,j) > 0.5) = 1;
   // next one is needed in the general case but not for TSP
   // cutcoeff(curcut, i, j)$(x.l(i,j) < 0.5) = -1;
   allcuts(curcut) = yes;      // include this cut in set
   curcut(cc) = curcut(cc-1);  // get next element
   solve tspcut using mip minimizing z;
   tspcut.solPrint = %solPrint.Quiet%;
);

* print solution in proper order
Set xtour 'ordered tour';
from(i)    = ord(i) = 1;      // initialize from to first city
visited(i) = no;
ok = 1;

loop(t$ok,
   next(j) = x.l(from,j) > 0.5;     // find next city
   xtour(t,from,next) = yes;
   visited(from) = yes;
   from(j)       = next(j);
   ok$sum(visited(next),1) = 0;     // we have detected a subtour
);

option  xtour:0:0:1;
display xtour,x.l;

abort$(card(allcuts) = card(cc)) "Too many cuts needed";