awktsp.gms : Traveling Salesman Problem Instance prepared with AWK

Description

The model writes an AWK script on the fly to process the input file
format defined by the maintainers of the TSPLib. More input instances
are available from

http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/

Keywords: mixed integer linear programming, traveling salesman problem,
          iterative subtour elimination, TSPLib, awk script


Reference

  • Juenger, M, Reinelt, G, and Thienel, S, Optimal and Probably Good Solutions for the Symmetric Traveling Salesman Problem. Zeitschrift fuer Operations Research 40 (1994), 183–217.

Small Model of Type : MIP


Category : GAMS Model library


Main file : awktsp.gms   includes :  p43.inc

$title Traveling Salesman Problem Instance prepared with AWK (AWKTSP,SEQ=298)

$onText
The model writes an AWK script on the fly to process the input file
format defined by the maintainers of the TSPLib. More input instances
are available from

http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/

Keywords: mixed integer linear programming, traveling salesman problem,
          iterative subtour elimination, TSPLib, awk script
$offText

$set fn p43.inc
$if not exist %fn% $abort %fn% ist not present

$echoN "$setGlobal n " > %gams.scrdir%n.%gams.scrext%
$call grep DIMENSION %fn% | cut -d: -f2 >> "%gams.scrdir%n.%gams.scrext%"
$include %gams.scrdir%n.%gams.scrext%

$onEcho > %gams.scrdir%x.%gams.scrext%
BEGIN                  { i=1 }
/^EDGE_WEIGHT_TYPE/    { if ( $2 != "EXPLICIT" )    error("Wrong type")   }
/^EDGE_WEIGHT_FORMAT/  { if ( $2 != "FULL_MATRIX" ) error("Wrong format") }
/^EDGE_WEIGHT_SECTION/ { readM = 1; next }
/^EOF/                 { exit }
readM == 1             { for (k=1; k <= NF; k++) print "i" i,"i" j+k,$k;
                         if (j+NF < %n%) j += NF; else { i++; j=0 }       }
function error(s) { print("--- " s ". Exiting.");  exit; }
$offEcho

$call awk -f "%gams.scrdir%x.%gams.scrext%" %fn% > "%gams.scrdir%data.%gams.scrext%"

Set
   ii    'cities'                                       / i1*i%n% /
   i(ii) 'subset of cities to fit GAMS demo model size' / i1*i7   /;

Alias (ii,jj), (i,j,k);

Parameter c(ii,jj) /
$onDelim
$include %gams.scrdir%data.%gams.scrext%
$offDelim
/;

Variable
   x(ii,jj) 'decision variables - leg of trip'
   z        'objective variable';

Binary Variable x;

Equation
   objective  'total cost'
   rowsum(ii) 'leave each city only once'
   colsum(jj) 'arrive at each city only once';

* The assignment problem is a relaxation of the TSP
objective.. z =e= sum((i,j), c(i,j)*x(i,j));

rowsum(i).. sum(j, x(i,j)) =e= 1;

colsum(j).. sum(i, x(i,j)) =e= 1;

* exclude diagonal
x.fx(ii,ii) = 0;

Set ij(ii,jj) 'exclude first row and column';
ij(ii,jj) = ord(ii) > 1 and ord(jj) > 1;

option optCr = 0, optCa = 0.99;

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'
   from(i)     'contains always one element: the from city'
   next(j)     'contains always one element: the to city'
   visited(i)  'flag whether a city is already visited'
   tt(t)       'contains always one element: the current subtour';

Alias (i,ix);

$eolCom //

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

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) = no;
   tt(t)   = no;
   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) = no;                  // find city visited after city 'from'
      loop((from,j),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(j)  = no;           // make sure we only have one element turned on
            from(ix) = yes;
          );
      );
   );
   display tour;
   nosubtours = sum(t, max(0,smax(tour(i,j,t),1)));
   display nosubtours;

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

   // else: 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";