tsp1.gms : Traveling Salesman Problem - One

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:

```

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:

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";
``````
GAMS Development Corp.
GAMS Software GmbH

General Information and Sales
U.S. (+1) 202 342-0180
Europe: (+49) 221 949-9170