tsp4.gms : Traveling Salesman Problem - Four

Description

```This is the fourth problem in a series of traveling salesman
problems. Here we revisit TSP1 and generate smarter cuts.
The first relaxation is the same as in TSP1.
```

Reference

• Kalvelagen, E, Model Building with GAMS. forthcoming

Large Model of Type : MIP

Category : GAMS Model library

Main file : tsp4.gms   includes :  br17.inc

``````\$title Traveling Salesman Problem - Four (TSP4,SEQ=180)

\$onText
This is the fourth problem in a series of traveling salesman
problems. Here we revisit TSP1 and generate smarter cuts.
The first relaxation is the same as in TSP1.

Kalvelagen, E, Model Building with GAMS. forthcoming

de Wetering, A V, private communication.

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

\$eolCom //

\$include br17.inc

* For this algorithm we can try a larger subset of 12 cities.
Set i(ii) / i1*i12 /;

* 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";

Set
tour(i,j,t) 'subtours'
visited(i)  'flag whether a city is already visited';

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

Alias (i,ix);

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

* subtour elimination by adding cuts
Set cc / c1*c1000 /;

Alias(cc,ccc); // we allow up to 1000 cuts

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

Parameter
cutcoeff(cc, i, j)
rhs(cc)
nosubtours 'number of subtours';

Equation cut(cc) 'dynamic cuts';

cut(allcuts).. sum((i,j), cutcoeff(allcuts,i,j)*x(i,j)) =l= rhs(allcuts);

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

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

Scalar ok;

loop(ccc,
*  initialize
from(i)\$(ord(i) = 1) = yes;    // turn first element on
tt(t)\$(  ord(t) = 1) = yes;    // turn first element on
tour(i,j,t) = no;
visited(i)  = no;
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(ix\$(not visited(ix)),       // find starting point of new subtour
from(ix) = yes;
);
);
);
display tour;
nosubtours = sum(t, max(0,smax(tour(i,j,t),1)));
display nosubtours;

break\$(nosubtours = 1); // done: no subtours

// introduce cut
loop(t\$(ord(t) <= nosubtours),
rhs(curcut) = -1;
loop(tour(i,j,t),
cutcoeff(curcut, i, j)\$(x.l(i,j) > 0.5) = 1;
* not needed due to nature of assignment constraints
*        cutcoeff(curcut, i, j)\$(x.l(i,j) < 0.5) = -1;
rhs(curcut) = rhs(curcut) + 1;
);
allcuts(curcut) = yes;   // include this cut in set
curcut(cc) = curcut(cc-1);
);
solve tspcut using mip minimizing z;
tspcut.solPrint = %solPrint.quiet%;
tspcut.limRow   = 0;
tspcut.limCol   = 0;
);

display x.l;
abort\$(nosubtours <> 1) "Too many cuts needed";
``````