fiveleap.gms : The Five Leaper Tour Problem

Description

Just as the knight makes moves of length root-5 that have coordinates {1,2}, a
fiveleaper is a type of generalized knight that makes moves of length 5 units,
with coordinates either {0,5} or {3,4}. In either event the Euclidean distance
traveled is five squares.

A tour requires that the fiveleaper visits every square on a board once and once
only using legal moves. The start and finish squares must be separated by a
legal move and the fiveleaper could close the tour by making this final move.

Run with parameters NROW, NCOL (size of chess board, default 8x8), and MAXCUT
(maximum number of subtour elimination cuts, default 500). For example,

gams fiveleap --NROW=10 --NCOL=10 --MAXCUT=1000

More information on leapers at http://pubsonline.informs.org/doi/pdf/10.1287/ited.4.1.78


References


Large Model of Type : MIP


Category : GAMS Model library


Main file : fiveleap.gms

$title The Five Leaper Tour Problem (FIVELEAP,SEQ=268)

$onText
Just as the knight makes moves of length root-5 that have coordinates {1,2}, a
fiveleaper is a type of generalized knight that makes moves of length 5 units,
with coordinates either {0,5} or {3,4}. In either event the Euclidean distance
traveled is five squares.

A tour requires that the fiveleaper visits every square on a board once and once
only using legal moves. The start and finish squares must be separated by a
legal move and the fiveleaper could close the tour by making this final move.

Run with parameters NROW, NCOL (size of chess board, default 8x8), and MAXCUT
(maximum number of subtour elimination cuts, default 500). For example,

gams fiveleap --NROW=10 --NCOL=10 --MAXCUT=1000

More information on leapers at http://pubsonline.informs.org/doi/pdf/10.1287/ited.4.1.78


Chlond, M J, Daniel, R C, and Heipcke, S, Fiveleapers a-leaping.
http://pubsonline.informs.org/doi/pdf/10.1287/ited.4.1.78

Gueret, C, Prins, C, and Sevaux, M, Applications of Optimization with Xpress-MP,
Translated and revised by Susanne Heipcke. Dash Optimization, 2002.

Keywords: mixed integer linear programming, subtour elimination, mathematical games,
          fiveleaper tour problem
$offText

$eolCom //
$if not set NCOL   $set NCOL 8
$if not set NROW   $set NROW 8
$if not set MAXCUT $set MAXCUT 500

Set
   r          'rows'         / 1*%NCOL% /
   c          'columns'      / 1*%NROW% /
   ss(r,c)    'start square' / '1'.'1'  /
   m(r,c,r,c) 'legal moves';

Alias (r,rp), (c,cp);

Variable
   xm(r,c,r,c) 'moves of a tour'
   nm(r,c)     'number of move'
   z           'dummy objective variable';

Binary   Variable xm;
Positive Variable nm;

Set
   nn            'subtour elimination cuts' / 1*%MAXCUT% /
   t(nn,r,c,r,c) 'subtour'
   n(nn)         'active cuts';

Parameter
   l(nn) 'length of subtour';

Equation
   obj               'dummy objective'
   deffrom(r,c)      'each square precedes one other'
   defto(r,c)        'each square is preceded by one other'
   deforder(r,c,r,c) 'order the moves'
   defsecut(nn)      'subtour elimination constraint';

obj..          z =e= sum(m, xm(m));

deffrom(r,c).. sum(m(r,c,rp,cp), xm(m)) =e= 1;

defto(rp,cp).. sum(m(r,c,rp,cp), xm(m)) =e= 1;

deforder(m(r,c,rp,cp))$(not ss(rp,cp)).. nm(r,c) - nm(rp,cp) =l= %NCOL%*%NROW%*(1 - xm(m)) - 1;

defsecut(n)..  sum(t(n,m), xm(m)) =l= l(n)-1;

Model
   leaper   'closed formulation of 5 leaper'  / obj, deffrom, defto, deforder /
   leaperSE 'subtour elimination formulation' / obj, deffrom, defto, defsecut /;

m(r,c,rp,cp) = sqr(ord(r) - ord(rp)) + sqr(ord(c) - ord(cp)) = 25; // possible moves

Set NoExit(r,c) "squares that don't allow any moves";

NoExit(r,c) = sum(m(r,c,rp,cp),1) = 0;
abort$card(NoExit) NoExit;

Parameter
   leaperTour(r,c) 'leaper solution'
   SolRep          'solution timing report';

option solPrint = off, limRow = 0, limCol = 0, t:0:0:1, leaperTour:0:1:1;

SolRep('%NCOL%x%NROW%','#Moves') = card(m);

nm.fx(ss)      =   1; // We start the leaper tour from the start square = 1,1
leaper.resLim  = 120; // Run the closed leaper formulation for at most 120 seconds
solve leaper minimizing z using mip;

if(leaper.modelStat = %modelStat.optimal% or
   leaper.modelStat = %modelStat.integerSolution%, // Did we find an integer solution?
   leaperTour(r,c)  = nm.l(r,c);
   SolRep('Closed','Time') = leaper.resUsd;
   display 'Closed Formulation Tour', leaperTour;
else
   SolRep('Closed','Time') = na;
   display 'No Solution for closed leaper model';
);

Set
   from(r,c)
   to(r,c)      'tour searching sets'
   nl(nn)       'last active cuts'
   visited(r,c) 'squares visited in tour search';

Scalar
   ntours 'number of tours in current solution'
   ttours 'total number of tours' / 0 /;

SolRep('SubTour','Time') = 0;
leaperSE.solPrint = %solPrint.quiet%; // Don't give any solver output

* Initialize the subtour elimination data structures
nl('1') = yes;
n(nn)   =  no;
t(nn,m) =  no;
l(nn)   =   0;

repeat
   solve  leaperSE minimizing z using mip;
   abort$(leaperSE.modelStat <> %modelStat.optimal% and
          leaperSE.modelStat <> %modelStat.integerSolution% ) 'No integer solution found!', t;
   SolRep('SubTour','Time') = SolRep('SubTour','Time') + leaperSE.resUsd;
   xm.l(m) = round(xm.l(m));
   ntours  = 0;
   visited(r,c) = no;

   loop((r,c)$(not visited(r,c)), // Loop through all unvisited squares
      ntours    = ntours + 1;
      nl(nn)    = nl(nn - 1);
      n(nl)     = yes;
      l(nl)     =   0;
      from(r,c) = yes;            // Start the (sub)tour
      repeat
         visited(from) = yes;
         to(rp,cp)     = sum(m(from,rp,cp), xm.l(m)); // Where does the move go
         t(nl,from,to) = yes;
         l(nl)         = l(nl) + 1;
         from(rp,cp)   = to(rp,cp); // The destination of the move becomes the
                                    // origin of the next move
      until sum(visited(to),1);
      from(r,c) = no;
   );
   ttours = ttours + ntours;
   abort$(ttours > card(nn)) 'Cut set nn too small', t, n;
until ntours = 1;

SolRep('SubTour','Iterations') = leaperSE.number;
SolRep('SubTour','#SubTours')  = ttours;

* Construct the leaper tour
Scalar nmove 'number of move' / 0 /;
from(ss) = yes;

repeat
   nmove     = nmove + 1;
   to(rp,cp) = sum(m(from,rp,cp), xm.l(m));
   leaperTour(from) = nmove;
   from(r,c) = to(r,c);
until to('1','1');

display 'SubTour Elimination Tour', leaperTour, SolRep;