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
|
© 2001-2020 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.