Fiveleaper (MIP model and graphics)
|
|
|
| Type: | Traveling Salesman Problem |
| Rating: | 4 (medium-difficult) |
| Description: | A fiveleaper travels over the chessboard by advancing in a single move either 5 squares in a straight line or three squares in a particular direction and 4 in an orthogonal direction. That is, with every move it travels a Euclidean distance of five squares. The problem of finding fiveleaper's tours on a chessboard is an instance of the Traveling Salesman Problem (TSP) and we adapt the subtour elimination algorithm described in the book 'Applications of optimization with Xpress-MP' (problem f5tour) for solving this problem. You will find a description of this problem and a few other model versions in the following publication: M.J. Chlond, B. Daniel, S. Heipcke, Fiveleapers a-leaping, INFORMS Transactions on Education, Vol. 4, No. 1, 2003. http://ite.pubs.informs.org/Vol4No1/ChlondDanielHeipcke The model version fiveleap_graph.mos displays a user graph within a webbrowser. The model fiveleap.mos simply prints out the results and will work on any platform for which Mosel is available. |
| File(s): | fiveleap.mos, fiveleap_graph.mos |
|
|
|
| fiveleap.mos |
(!******************************************************
Mosel Example Problems
======================
file fiveleap.mos
`````````````````
Fiveleaper problem.
Closed TSP form of 5leaper for a rectangular chessboard
Run with parameters NROW and NCOL (numbers of squares on the edges)
e.g. mosel exe fiveleap NROW=9 NCOL=6
NROW=NCOL=8 are the smallest possible values for square boards.
This is a variant of the problem in "f5tour.mos" from the book
"Applications of optimization with Xpress-MP"
You will find a description of this problem at the following address:
https://doi.org/10.1287/ited.4.1.78
A square (i,j) on the rectangle is labeled
sq := j + NCOL*(i-1)
Given a square label
i := ceil(sq/NCOL)
j := sq - NCOL*(i-1)
(c) 2008 Fair Isaac Corporation
authors: Bob Daniel, S. Heipcke, March 2003
*******************************************************!)
model 'FIVELEAP'
uses 'mmxprs', 'mmsystem'
parameters
NCOL = 8 ! Number of colums
NROW = 8 ! Number of rows
end-parameters
forward function break_subtour: integer
forward procedure print_sol
forward procedure find_subtour(start: integer, TOUR: set of integer)
declarations
NSQ = NCOL*NROW ! Number of squares
RSQ = 1..NSQ ! Range of squares
nmoves, ntours, niterations, ntourstotal: integer
nmovesfrom: array(RSQ) of integer ! Counts possible moves leaving
x: dynamic array(RSQ,RSQ) of mpvar ! 1 if we leap from sq1 to sq2
NEXTX: array(RSQ) of integer ! Next square after sq in the solution
square1, square2, ii, jj: integer
end-declarations
! For each pair of squares with a valid move...
nmoves := 0
forall(i1,i2 in 1..NCOL, j1,j2 in 1..NROW | (i1-i2)^2+(j1-j2)^2 = 25) do
square1 := j1+NCOL*(i1-1)
square2 := j2+NCOL*(i2-1)
create(x(square1,square2)) ! Create the 'x' binary decision variable
x(square1,square2) is_binary
nmovesfrom(square1) += 1 ! Note a possible move from square
nmoves += 1
end-do
writeln("There are ", nmoves, " possible moves")
! Check that each square is reachable
forall(sq in RSQ | nmovesfrom(sq)=0) do
ii := ceil(sq/NCOL)
jj := sq-NCOL*(ii-1)
writeln("**** Cannot go anywhere from square (", ii, ",", jj, ")")
exit(0)
end-do
! Objective (arbitrary)
AnyObj := sum(sq1,sq2 in RSQ | exists(x(sq1,sq2)) ) x(sq1,sq2)
! Each square precedes one other
forall(sq1 in RSQ) sum(sq2 in RSQ | exists(x(sq1,sq2)) ) x(sq1,sq2) = 1
! Each cell is preceded by one other
forall(sq2 in RSQ) sum(sq1 in RSQ | exists(x(sq1,sq2)) ) x(sq1,sq2) = 1
! Optimizer settings to speed up the iterations
setparam("XPRS_CUTSTRATEGY", 0)
setparam("XPRS_PRESOLVE", 0)
! Solve the problem
starttime := gettime
niterations := 0
while (TRUE) do
minimize(AnyObj)
if (getprobstat <> XPRS_OPT) then
writeln("Problem is infeasible.")
exit(0)
end-if
forall(sq in RSQ)
NEXTX(sq):= integer(round(getsol(sum(sq2 in RSQ) sq2*x(sq,sq2) )))
ntours := break_subtour
if (ntours=1) then break; end-if
! Print a log every 10 iterations
niterations += 1
ntourstotal += ntours
if (niterations mod 10 = 0) then
writeln(niterations, " (", gettime-starttime, " sec) tours eliminated: ",
ntourstotal)
end-if
end-do
print_sol
writeln("Total time: ", gettime-starttime, " sec")
!-----------------------------------------------------------------
! Eliminate all subtours, and return number of (sub)tours
! - Find news subtours starting at each node in turn
! - If found complete tour, return 1
! - Otherwise add subtour elimination cut and continue
!
! Global variables required
! RSQ: range of squares
! NSQ: number of squares
! NEXTX(i): square following i in current solution
function break_subtour: integer
declarations
TOUR, ALLTOURS: set of integer
ntours: integer
end-declarations
ALLTOURS := {}
ntours := 0
forall(startsquare in RSQ | startsquare not in ALLTOURS) do
! Find (sub)tour containing {startsquare}
find_subtour(startsquare, TOUR)
ALLTOURS += TOUR
ntours += 1
! If found complete tour, return
if (getsize(TOUR)>=NSQ) then break; end-if
! Add a subtour breaking constraint
sum(sq in TOUR) x(sq,NEXTX(sq)) <= getsize(TOUR) - 1
end-do
returned := ntours
end-function
!-----------------------------------------------------------------
! Find a subtour starting at square 'start'; result returned in TOUR
procedure find_subtour(start: integer, TOUR: set of integer)
declarations
square: integer
end-declarations
TOUR := {}
square := start
repeat
TOUR += {square}
square := NEXTX(square)
until (square=start)
end-procedure
!-----------------------------------------------------------------
! Print the current solution
!
! Global variables required
! RSQ: range of squares
! NEXTX(i): square following i in current solution
procedure print_sol
declarations
SEENSOFAR: set of integer
square: integer
end-declarations
SEENSOFAR:={}
forall(startsquare in RSQ | startsquare not in SEENSOFAR) do
write(startsquare)
square := startsquare
repeat
SEENSOFAR += {square}
square := NEXTX(square)
write(" - ", square)
until (square=startsquare)
writeln(' ')
end-do
end-procedure
end-model
|
| fiveleap_graph.mos |
(!******************************************************
Mosel Example Problems
======================
file fiveleap_graph.mos
```````````````````````
Fiveleaper problem.
Closed TSP form of 5leaper for a rectangular chessboard
- Graphical representation of solutions -
Run with parameters NROW and NCOL (numbers of squares on the edges)
e.g. mosel exe fiveleap NROW=9 NCOL=6
NROW=NCOL=8 are the smallest possible values for square boards.
This is a variant of the problem in "f5tour.mos" from the book
"Applications of optimization with Xpress-MP"
You will find a description of this problem at the following address:
https://doi.org/10.1287/ited.4.1.78
A square (i,j) on the rectangle is labeled
sq := j + NCOL*(i-1)
Given a square label
i := ceil(sq/NCOL)
j := sq - NCOL*(i-1)
(c) 2008 Fair Isaac Corporation
authors: Bob Daniel, S. Heipcke, March 2003, rev. Sep. 2017
*******************************************************!)
model 'FIVELEAPGR'
uses 'mmxprs', 'mmsystem', 'mmsvg'
parameters
NCOL = 8 ! Number of colums
NROW = 8 ! Number of rows
DISPLAY = true ! `true' to see graphical output
end-parameters
forward function break_subtour: integer
forward procedure print_sol
forward procedure draw_sol
forward procedure find_subtour(start: integer, TOUR: set of integer)
declarations
NSQ = NCOL*NROW ! Number of squares
RSQ = 1..NSQ ! Range of squares
nmoves, ntours, niterations, ntourstotal: integer
nmovesfrom: array(RSQ) of integer ! Counts possible moves leaving
x: dynamic array(RSQ,RSQ) of mpvar ! 1 if we leap from sq1 to sq2
NEXTX: array(RSQ) of integer ! Next square after sq in the solution
square1, square2, ii, jj: integer
end-declarations
! For each pair of squares with a valid move...
nmoves := 0
forall(i1,i2 in 1..NCOL, j1,j2 in 1..NROW | (i1-i2)^2+(j1-j2)^2 = 25) do
square1 := j1+NCOL*(i1-1)
square2 := j2+NCOL*(i2-1)
create(x(square1,square2)) ! Create the 'x' binary decision variable
x(square1,square2) is_binary
nmovesfrom(square1) += 1 ! Note a possible move from square
nmoves += 1
end-do
writeln("There are ", nmoves, " possible moves")
! Check that each square is reachable
forall(sq in RSQ | nmovesfrom(sq)=0) do
ii := ceil(sq/NCOL)
jj := sq-NCOL*(ii-1)
writeln("**** Cannot go anywhere from square (", ii, ",", jj, ")")
exit(0)
end-do
! Objective (arbitrary)
AnyObj := sum(sq1,sq2 in RSQ | exists(x(sq1,sq2)) ) x(sq1,sq2)
! Each square precedes one other
forall(sq1 in RSQ) sum(sq2 in RSQ | exists(x(sq1,sq2)) ) x(sq1,sq2) = 1
! Each cell is preceded by one other
forall(sq2 in RSQ) sum(sq1 in RSQ | exists(x(sq1,sq2)) ) x(sq1,sq2) = 1
! Optimizer settings to speed up the iterations
setparam("XPRS_CUTSTRATEGY", 0)
setparam("XPRS_PRESOLVE", 0)
! Solve the problem
starttime := gettime
niterations := 0
while (TRUE) do
minimize(AnyObj)
if (getprobstat <> XPRS_OPT) then
writeln("Problem is infeasible.")
exit(0)
end-if
forall(sq in RSQ)
NEXTX(sq):= integer(round(getsol(sum(sq2 in RSQ) sq2*x(sq,sq2) )))
if DISPLAY then
draw_sol
! Closing the graphical display will interrupt the algorithm
if svgclosing then break; end-if
end-if
ntours := break_subtour
if (ntours=1) then break; end-if
! Print a log every 10 iterations
niterations += 1
ntourstotal += ntours
if (niterations mod 10 = 0) then
writeln(niterations, " (", gettime-starttime, " sec) tours eliminated: ",
ntourstotal)
end-if
end-do
print_sol
writeln("Total time: ", gettime-starttime, " sec")
if DISPLAY then
svgwaitclose("Close browser window to terminate model execution.", 1)
end-if
!-----------------------------------------------------------------
! Eliminate all subtours, and return number of (sub)tours
! - Find news subtours starting at each node in turn
! - If found complete tour, return 1
! - Otherwise add subtour elimination cut and continue
!
! Global variables required
! RSQ: range of squares
! NSQ: number of squares
! NEXTX(i): square following i in current solution
function break_subtour: integer
declarations
TOUR, ALLTOURS: set of integer
ntours: integer
end-declarations
ALLTOURS := {}
ntours := 0
forall(startsquare in RSQ | startsquare not in ALLTOURS) do
! Find (sub)tour containing {startsquare}
find_subtour(startsquare, TOUR)
ALLTOURS += TOUR
ntours += 1
! If found complete tour, return
if (getsize(TOUR)>=NSQ) then break; end-if
! Add a subtour breaking constraint
sum(sq in TOUR) x(sq,NEXTX(sq)) <= getsize(TOUR) - 1
end-do
returned := ntours
end-function
!-----------------------------------------------------------------
! Find a subtour starting at square 'start'; result returned in TOUR
procedure find_subtour(start: integer, TOUR: set of integer)
declarations
square: integer
end-declarations
TOUR := {}
square := start
repeat
TOUR += {square}
square := NEXTX(square)
until (square=start)
end-procedure
!-----------------------------------------------------------------
! Print the current solution
!
! Global variables required
! RSQ: range of squares
! NEXTX(i): square following i in current solution
procedure print_sol
declarations
SEENSOFAR: set of integer
square: integer
end-declarations
SEENSOFAR:={}
forall(startsquare in RSQ | startsquare not in SEENSOFAR) do
write(startsquare)
square := startsquare
repeat
SEENSOFAR += {square}
square := NEXTX(square)
write(" - ", square)
until (square=startsquare)
writeln(' ')
end-do
end-procedure
!-----------------------------------------------------------------
! Draw the current solution
!
! Global variables required
! RSQ: range of squares
! NEXTX(sq): square following sq in current solution
! NCOL: number of columns
procedure draw_sol
declarations
SEENSOFAR: set of integer
tour, square, gr, ii1, ii2, jj1, jj2: integer
end-declarations
if DISPLAY then
svgerase
svgsetgraphscale(25)
! maxval:=maxlist(NCOL+1,NROW+2)
! svgsetgraphviewbox(0,0,maxval,maxval)
! Draw the board
svgaddgroup("B", "", SVG_BLACK)
forall(i in 1..NROW+1) svgaddline(i-0.5, 0.5, i-0.5, NCOL+0.5)
forall(j in 1..NCOL+1) svgaddline(0.5, j-0.5, NROW+0.5, j-0.5)
SEENSOFAR := {}
tour := 0
forall(tour as counter, startsquare in RSQ | startsquare not in SEENSOFAR) do
svgaddgroup("G"+tour, "Tour "+tour)
square := startsquare
repeat
ii1 := ceil(square/NCOL)
jj1 := square-NCOL*(ii1-1)
ii2 := ceil(NEXTX(square)/NCOL)
jj2 := NEXTX(square)-NCOL*(ii2-1)
svgaddarrow(ii1, jj1, ii2, jj2)
SEENSOFAR += {square}
square := NEXTX(square)
until (square=startsquare)
end-do
svgaddtext("B",1,NROW+1,"Number of (sub)tours: "+tour)
svgrefresh
! Uncomment next line to pause at every iteration:
if tour>1 then svgpause; end-if
end-if
end-procedure
end-model
|