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 https://dx.doi.org/10.1287/ited.4.1.78
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 https://dx.doi.org/10.1287/ited.4.1.78
Chlond, M J, Daniel, R C, and Heipcke, S, Fiveleapers a-leaping.
https://dx.doi.org/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;