Fantasy OR: Sangraal (CP and MIP models)
|
|
|
| Type: | Scheduling |
| Rating: | 3 (intermediate) |
| Description: | The Sangraal problem is an example of a mathematical problem embedded in a computer fantasy game. The description of the problem and the mathematical model introduced below draw on a publication by M.Chlond: M.J. Chlond, Fantasy OR, INFORMS Transactions on Education, Vol. 4, No. 3, 2004. http://ite.pubs.informs.org/Vol4No3/Chlond/ When the Sangraal (Holy Grail) is almost won the hero arrives at a castle where he finds 8 imprisoned knights. He is facing the task to bring the largest possible number of knights for the arrival of the Sangraal in twenty minutes' time. The time required for freeing a knight depends on his state of binding. A freed knight then needs a given amount of time to wash and recover himself physically. For every knight, the durations of freeing and preparing are given. The problem of deciding in which order to free the knights is a standard scheduling problem, or to be more precise the problem of sequencing a set of disjunctive tasks. Typical objective functions in scheduling are to minimize the completion time of the last task (the so-called makespan) or the average completion time of all tasks. The objective to maximize the number of knights who are ready by a given time makes the problem slightly more challenging since we need to introduce additional variables for counting the knights who are ready on time.
|
| File(s): | sangraal.mos, sangraal_graph.mos, sangraalind.mos, sangraal_ka.mos, sangraal2_ka.mos |
|
|
|
| sangraal.mos |
(!******************************************************
Mosel Example Problems
======================
file sangraal.mos
`````````````````
Sangraal problem.
When the Sangraal (Holy Grail) is almost won the hero arrives
at a castle where he finds 8 imprisoned knights. He is facing
the task to bring the largest possible number of knights for
the arrival of the Sangraal in twenty minutes' time. The time
required for freeing a knight depends on his state of binding.
A freed knight then needs a given amount of time to wash and
recover himself physically.
Description and original model by M. Chlond:
https://doi.org/10.1287/ited.4.3.66
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, 2005, rev. June 2011
*******************************************************!)
model Sangraal
uses "mmxprs", "mmjobs"
forward public procedure print_solution
declarations
KNIGHTS = {"Agravain", "Bors", "Caradoc", "Dagonet", "Ector", "Feirefiz",
"Gareth", "Harry"}
K = 8
POS = 1..K
FREE: array(KNIGHTS) of real ! Time to free each knight
PREP: array(KNIGHTS) of real ! Time to prepare each knight
x: array(KNIGHTS,POS) of mpvar ! x(k,j)=1 if knight k in position j,
! 0 otherwise
ontime: array(POS) of mpvar ! ontime(j)=1 if position j finished within
! 20 minutes, 0 otherwise
ready: array(POS) of mpvar ! Finish time for each position
SOLFOUND = 2 ! Solution found event
pos: array(KNIGHTS) of integer ! Position of knight
end-declarations
FREE("Agravain"):=1; PREP("Agravain"):=15
FREE("Bors") :=1; PREP("Bors") := 5
FREE("Caradoc") :=2; PREP("Caradoc") :=15
FREE("Dagonet") :=2; PREP("Dagonet") := 5
FREE("Ector") :=3; PREP("Ector") :=10
FREE("Feirefiz"):=4; PREP("Feirefiz"):=15
FREE("Gareth") :=5; PREP("Gareth") :=10
FREE("Harry") :=6; PREP("Harry") := 5
MAXT:= sum(k in KNIGHTS) FREE(k) + max(k in KNIGHTS) PREP(k)
MINT:= min(k in KNIGHTS) (PREP(k) + FREE(k))
forall(k in KNIGHTS, j in POS) x(k,j) is_binary
forall(j in POS) ontime(j) is_binary
! Maximize number of positions finished within 20 minutes
TotalFreed := sum(j in POS) ontime(j)
! Each knight in one position
forall(k in KNIGHTS) sum(j in POS) x(k,j) = 1
! Each position has one knight
forall(j in POS) sum(k in KNIGHTS) x(k,j) = 1
! Compute finish time for each position
forall(j in POS)
sum(k in KNIGHTS,l in 1..j-1) FREE(k)*x(k,l) +
sum(k in KNIGHTS) (FREE(k)+PREP(k))*x(k,j) = ready(j)
! ontime(j) = 1 if knight in position j is freed and prepared within 20 min.
forall(j in POS) do
ready(j) >= 21-(21-MINT)*ontime(j)
ready(j) <= MAXT-(MAXT-20)*ontime(j)
end-do
! setparam("XPRS_VERBOSE", true)
! setparam("XPRS_HEURSTRATEGY", 0)
! setparam("XPRS_CUTSTRATEGY", 0)
! setparam("XPRS_PRESOLVE", 0)
setcallback(XPRS_CB_INTSOL,"print_solution")
maximize(TotalFreed)
!********************************************************************
public procedure print_solution
obj:=getparam("XPRS_LPOBJVAL")
writeln("Number of knights freed on time: ", obj)
writeln("Knight Position Ready <=20 min")
forall(k in KNIGHTS) do
pos(k):=round(getsol(sum(j in POS) j*x(k,j)))
writeln(strfmt(k,-12), pos(k), " ", strfmt(getsol(ready(pos(k))),2),
" ", if(getsol(ontime(pos(k)))=1,"yes","no"))
end-do
end-procedure
end-model
|
| sangraal_graph.mos |
(!******************************************************
Mosel Example Problems
======================
file sangraal.mos
`````````````````
Sangraal problem.
- Graphical representation of solutions -
When the Sangraal (Holy Grail) is almost won the hero arrives
at a castle where he finds 8 imprisoned knights. He is facing
the task to bring the largest possible number of knights for
the arrival of the Sangraal in twenty minutes' time. The time
required for freeing a knight depends on his state of binding.
A freed knight then needs a given amount of time to wash and
recover himself physically.
Description and original model by M. Chlond:
https://doi.org/10.1287/ited.4.3.66
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, 2005, rev. Mar. 2019
*******************************************************!)
model Sangraal
uses "mmxprs", "mmsvg"
forward public procedure print_solution
declarations
KNIGHTS = {"Agravain", "Bors", "Caradoc", "Dagonet", "Ector", "Feirefiz",
"Gareth", "Harry"}
K = 8
POS = 1..K
FREE: array(KNIGHTS) of real ! Time to free each knight
PREP: array(KNIGHTS) of real ! Time to prepare each knight
x: array(KNIGHTS,POS) of mpvar ! x(k,j)=1 if knight k in position j,
! 0 otherwise
ontime: array(POS) of mpvar ! ontime(j)=1 if position j finished within
! 20 minutes, 0 otherwise
ready: array(POS) of mpvar ! Finish time for each position
pos: array(KNIGHTS) of integer ! Position of knight
end-declarations
FREE("Agravain"):=1; PREP("Agravain"):=15
FREE("Bors") :=1; PREP("Bors") := 5
FREE("Caradoc") :=2; PREP("Caradoc") :=15
FREE("Dagonet") :=2; PREP("Dagonet") := 5
FREE("Ector") :=3; PREP("Ector") :=10
FREE("Feirefiz"):=4; PREP("Feirefiz"):=15
FREE("Gareth") :=5; PREP("Gareth") :=10
FREE("Harry") :=6; PREP("Harry") := 5
MAXT:= sum(k in KNIGHTS) FREE(k) + max(k in KNIGHTS) PREP(k)
MINT:= min(k in KNIGHTS) (PREP(k) + FREE(k))
forall(k in KNIGHTS, j in POS) x(k,j) is_binary
forall(j in POS) ontime(j) is_binary
! Maximize number of positions finished within 20 minutes
TotalFreed := sum(j in POS) ontime(j)
! Each knight in one position
forall(k in KNIGHTS) sum(j in POS) x(k,j) = 1
! Each position has one knight
forall(j in POS) sum(k in KNIGHTS) x(k,j) = 1
! Compute finish time for each position
forall(j in POS)
sum(k in KNIGHTS,l in 1..j-1) FREE(k)*x(k,l) +
sum(k in KNIGHTS) (FREE(k)+PREP(k))*x(k,j) = ready(j)
! ontime(j) = 1 if knight in position j is freed and prepared within 20 min.
forall(j in POS) do
ready(j) >= 21-(21-MINT)*ontime(j)
ready(j) <= MAXT-(MAXT-20)*ontime(j)
end-do
! setparam("XPRS_VERBOSE", true)
! Solve the problem, displaying every integer solution that is found
setcallback(XPRS_CB_INTSOL,"print_solution")
maximize(TotalFreed)
svgwaitclose("Close browser window to terminate model execution.", 1)
!********************************************************************
procedure draw_solution
svgerase ! Delete previous display
! Object group definitions (colors)
svgaddgroup("gontime", "Step 2 on time", SVG_GREEN)
svgsetstyle(SVG_STROKE,SVG_GREEN)
svgsetstyle(SVG_FILL,SVG_CURRENT)
svgsetstyle(SVG_FILLOPACITY,0.8)
svgaddgroup("gstep1", "Step 1 on time", SVG_GREEN)
svgsetstyle(SVG_STROKE,SVG_GREEN)
svgsetstyle(SVG_FILL,SVG_CURRENT)
svgsetstyle(SVG_FILLOPACITY,0.4)
svgaddgroup("glate", "Step 2 late", SVG_GRAY)
svgsetstyle(SVG_STROKE,SVG_GRAY)
svgsetstyle(SVG_FILL,SVG_CURRENT)
svgsetstyle(SVG_FILLOPACITY,0.8)
svgaddgroup("gstep1l", "Step 1 late", SVG_GRAY)
svgsetstyle(SVG_STROKE,SVG_GRAY)
svgsetstyle(SVG_FILL,SVG_CURRENT)
svgsetstyle(SVG_FILLOPACITY,0.4)
svgaddgroup("gtarget", "Target time",SVG_RED)
svgaddgroup("gax", "Axes", SVG_BLACK)
! Draw the tasks
prevt:=0.0; SCALE:=5
forall(j in POS) do
t1:=sum(k in KNIGHTS) FREE(k)*x(k,j).sol
t2:=sum(k in KNIGHTS) PREP(k)*x(k,j).sol
svgaddrectangle(if(prevt+t1<=21,"gstep1","gstep1l"), prevt, j*SCALE, t1, 0.8*SCALE)
prevt+=t1
svgaddrectangle(if(ontime(j).sol=1,"gontime","glate"), prevt, j*SCALE, t2, 0.8*SCALE)
end-do
! Draw some lines and display of the current objective value
svgaddline("gtarget",20,0.5*SCALE,20,(KNIGHTS.size+2)*SCALE)
svgaddarrow("gax",0,0.5*SCALE,max(j in POS) ready(j).sol + 5,0.5*SCALE)
svgaddarrow("gax",0,0.5*SCALE,0,(KNIGHTS.size+2)*SCALE)
svgaddtext("gax", 22, 1*SCALE, "Total on time="+TotalFreed.sol)
forall(k in KNIGHTS) svgaddtext("gax", -10, (pos(k)+0.25)*SCALE, k)
svgshowgraphaxes(false)
svgsetgraphviewbox(-12,-1, max(j in POS) ready(j).sol + 20,(KNIGHTS.size+4)*SCALE)
svgsetgraphscale(5)
svgrefresh ! Redraw the graph
! Uncomment next line to pause at every iteration:
svgpause
end-procedure
public procedure print_solution
obj:=getparam("XPRS_LPOBJVAL")
writeln("Number of knights freed on time: ", obj)
writeln("Knight Position Ready <=20 min")
forall(k in KNIGHTS) do
pos(k):=round(getsol(sum(j in POS) j*x(k,j)))
writeln(strfmt(k,-12), pos(k), " ", strfmt(getsol(ready(pos(k))),2),
" ", if(getsol(ontime(pos(k)))=1,"yes","no"))
end-do
draw_solution
end-procedure
end-model
|
| sangraalind.mos |
(!******************************************************
Mosel Example Problems
======================
file sangraalind.mos
````````````````````
Sangraal problem.
When the Sangraal (Holy Grail) is almost won the hero arrives
at a castle where he finds 8 imprisoned knights. He is facing
the task to bring the largest possible number of knights for
the arrival of the Sangraal in twenty minutes' time. The time
required for freeing a knight depends on his state of binding.
A freed knight then needs a given amount of time to wash and
recover himself physically.
Model formulation using indicator constraints.
Description and original model by M. Chlond:
https://doi.org/10.1287/ited.4.3.66
(c) 2010 Fair Isaac Corporation
author: S. Heipcke, Nov. 2010, rev. June 2011
*******************************************************!)
model Sangraal
uses "mmxprs", "mmjobs"
forward public procedure print_solution
declarations
KNIGHTS = {"Agravain", "Bors", "Caradoc", "Dagonet", "Ector", "Feirefiz",
"Gareth", "Harry"}
K = 8
POS = 1..K
FREE: array(KNIGHTS) of real ! Time to free each knight
PREP: array(KNIGHTS) of real ! Time to prepare each knight
x: array(KNIGHTS,POS) of mpvar ! x(k,j)=1 if knight k in position j,
! 0 otherwise
ontime: array(POS) of mpvar ! ontime(j)=1 if position j finished within
! 20 minutes, 0 otherwise
ready: array(POS) of mpvar ! Finish time for each position
pos: array(KNIGHTS) of integer ! Position of knight
end-declarations
FREE :: (["Agravain", "Bors", "Caradoc", "Dagonet", "Ector", "Feirefiz",
"Gareth", "Harry"])[1, 1, 2,2, 3, 4, 5,6]
PREP :: (["Agravain", "Bors", "Caradoc", "Dagonet", "Ector", "Feirefiz",
"Gareth", "Harry"])[15,5,15,5,10,15,10,5]
forall(k in KNIGHTS, j in POS) x(k,j) is_binary
forall(j in POS) ontime(j) is_binary
! Maximize number of positions finished within 20 minutes
TotalFreed := sum(j in POS) ontime(j)
! Each knight in one position
forall(k in KNIGHTS) sum(j in POS) x(k,j) = 1
! Each position has one knight
forall(j in POS) sum(k in KNIGHTS) x(k,j) = 1
! Compute finish time for each position
forall(j in POS)
sum(k in KNIGHTS,l in 1..j-1) FREE(k)*x(k,l) +
sum(k in KNIGHTS) (FREE(k)+PREP(k))*x(k,j) = ready(j)
! if ontime(j) = 1, then knight in position j is freed and prepared within
! 20 min. [ indicator constraint: ontime(j)=1 -> ready(j)<=20 ]
forall(j in POS)
indicator(1, ontime(j), ready(j)<=20)
setparam("XPRS_VERBOSE", true)
setcallback(XPRS_CB_INTSOL,"print_solution")
maximize(TotalFreed)
!********************************************************************
public procedure print_solution
obj:=getparam("XPRS_LPOBJVAL")
writeln("Number of knights freed on time: ", obj)
writeln("Knight Position Ready <=20 min")
forall(k in KNIGHTS) do
pos(k):=round(getsol(sum(j in POS) j*x(k,j)))
writeln(strfmt(k,-12), pos(k), " ", strfmt(getsol(ready(pos(k))),2),
" ", if(getsol(ontime(pos(k)))=1,"yes","no"))
end-do
end-procedure
end-model
|
| sangraal_ka.mos |
(!****************************************************************
CP example problems
===================
file sangraal_ka.mos
````````````````````
Sangraal scheduling problem.
When the Sangraal (Holy Grail) is almost won the hero arrives
at a castle where he finds 8 imprisoned knights. He is facing
the task to bring the largest possible number of knights for
the arrival of the Sangraal in twenty minutes' time. The time
required for freeing a knight depends on his state of binding.
A freed knight then needs a given amount of time to wash and
recover himself physically.
*** This model cannot be run with a Community Licence
for the provided data instance ***
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, 2005, rev. Jan. 2018
*****************************************************************!)
model "sangraal (CP)"
uses "kalis"
parameters
K = 8
end-parameters
forward public procedure print_solution
setparam("kalis_default_lb", 0)
declarations
KNIGHTS = 1..K
NAMES: array(KNIGHTS) of string ! Knights' names
FREE, PREP: array(KNIGHTS) of integer ! Durations of freeing/preparing
startF: array(KNIGHTS) of cpvar ! Start of freeing each knight
startP: array(KNIGHTS) of cpvar ! Start of preparing each knight
ontime: array(KNIGHTS) of cpvar ! ontime(i)=1 if knight i finished
! within 20 minutes, 0 otherwise
Disj: array(range) of cpctr ! Disjunction betw. freeing op.s
totalFreed,freedLate: cpvar ! Objective function variables
Strategy: array(range) of cpbranching ! Branching strategy
end-declarations
NAMES:: ["Agravain", "Bors", "Caradoc", "Dagonet", "Ector", "Feirefiz",
"Gareth", "Harry"]
FREE :: [1, 1, 2,2, 3, 4, 5,6]
PREP :: [15,5,15,5,10,15,10,5]
MAXT:= sum(i in KNIGHTS) FREE(i) + max(i in KNIGHTS) PREP(i)
! Define binary variables
forall(i in KNIGHTS) do
ontime(i) <= 1
startF(i) <= MAXT
startP(i) <= MAXT
end-do
! Every knight must be freed before he can prepare himself
forall(i in KNIGHTS) startF(i) + FREE(i) <= startP(i)
! Scheduling freeing operations (all disjunctive, i.e., one at a time)
ct:=1
forall(i,j in KNIGHTS | i<j) do
Disj(ct):= startF(i) + FREE(i) <= startF(j) or
startF(j) + FREE(j) <= startF(i)
Disj(ct) ! Post the constraint
ct+=1
end-do
! ontime(i) = 1 if knight i is freed and prepared within 20 minutes
forall(i in KNIGHTS) equiv( ontime(i)=1, startP(i)+PREP(i) <= 20 )
! Maximize number of positions finished within 20 minutes
totalFreed = sum(i in KNIGHTS) ontime(i)
freedLate = sum(i in KNIGHTS) (1-ontime(i))
! Define an enumeration strategy
Strategy(1):= assign_and_forbid(KALIS_LARGEST_MAX, KALIS_MAX_TO_MIN, ontime)
cp_set_branching(Strategy)
! Uncomment the followng line to use automatic linear relaxation
! setparam("kalis_auto_relax",true)
! Solve the problem
cp_set_solution_callback("print_solution")
! if not cp_minimize(freedLate) then
if not cp_maximize(totalFreed) then
writeln("Problem is infeasible")
exit(1)
end-if
cp_show_stats
!********************************************************************
! Solution printing
public procedure print_solution
writeln(" Freed Ready <=20 min")
forall(i in KNIGHTS)
writeln(strfmt(NAMES(i), -12), strfmt(getsol(startF(i)+FREE(i)),2),
" ", strfmt(getsol(startP(i)+PREP(i)),2), " ",
if(getsol(ontime(i))=1,"yes","no"))
writeln("Number of knights freed on time: ", getsol(totalFreed), "\n")
end-procedure
end-model
|
| sangraal2_ka.mos |
(!****************************************************************
CP example problems
===================
file sangraal2_ka.mos
`````````````````````
Sangraal scheduling problem.
- Formulation using tasks and resources -
When the Sangraal (Holy Grail) is almost won the hero arrives
at a castle where he finds 8 imprisoned knights. He is facing
the task to bring the largest possible number of knights for
the arrival of the Sangraal in twenty minutes' time. The time
required for freeing a knight depends on his state of binding.
A freed knight then needs a given amount of time to wash and
recover himself physically.
*** This model cannot be run with a Community Licence
for the provided data instance ***
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, 2006, rev. Jan. 2018
*****************************************************************!)
model "sangraal (CP)"
uses "kalis"
parameters
K = 8
end-parameters
forward public procedure print_solution
setparam("kalis_default_lb", 0)
declarations
KNIGHTS = 1..K
NAMES: array(KNIGHTS) of string ! Knights' names
FREE, PREP: array(KNIGHTS) of integer ! Durations of freeing/preparing
hero: cpresource ! Resource: the hero's time
taskF: array(KNIGHTS) of cptask ! Task of freeing each knight
taskP: array(KNIGHTS) of cptask ! Task of preparing each knight
ontime: array(KNIGHTS) of cpvar ! ontime(i)=1 if knight i finished
! within 20 minutes, 0 otherwise
Disj: array(range) of cpctr ! Disjunction betw. freeing op.s
totalFreed,freedLate: cpvar ! Objective function variables
Strategy: cpbranching ! Branching strategy
end-declarations
NAMES:: ["Agravain", "Bors", "Caradoc", "Dagonet", "Ector", "Feirefiz",
"Gareth", "Harry"]
FREE :: [1, 1, 2,2, 3, 4, 5,6]
PREP :: [15,5,15,5,10,15,10,5]
MAXT:= sum(i in KNIGHTS) FREE(i) + max(i in KNIGHTS) PREP(i)
! Setting up the resource (formulation of the disjunction of freeing tasks)
set_resource_attributes(hero, KALIS_UNARY_RESOURCE, 1)
! Setting up the tasks (durations and disjunctions)
forall(i in KNIGHTS) do
set_task_attributes(taskF(i), FREE(i), hero)
set_task_attributes(taskP(i), PREP(i))
end-do
! Define bounds on decision variables
forall(i in KNIGHTS) do
ontime(i) <= 1
getstart(taskF(i)) <= MAXT
getstart(taskP(i)) <= MAXT
end-do
! Every knight must be freed before he can prepare himself
forall(i in KNIGHTS) setsuccessors(taskF(i), {taskP(i)})
! ontime(i) = 1 if knight i is freed and prepared within 20 minutes
forall(i in KNIGHTS) equiv( ontime(i)=1, getend(taskP(i)) <= 20 )
! Maximize number of positions finished within 20 minutes
totalFreed = sum(i in KNIGHTS) ontime(i)
freedLate = sum(i in KNIGHTS) (1-ontime(i))
! Define a branching strategy
Strategy:= assign_and_forbid(KALIS_LARGEST_MAX, KALIS_MAX_TO_MIN, ontime)
cp_set_branching(Strategy)
! Solve the problem
cp_set_solution_callback("print_solution")
if not cp_maximize(totalFreed) then
writeln("Problem is infeasible")
exit(1)
end-if
cp_show_stats
!********************************************************************
! Solution printing
public procedure print_solution
writeln(" Freed Ready <=20 min")
forall(i in KNIGHTS)
writeln(strfmt(NAMES(i), -12), strfmt(getsol(getend(taskF(i))),2), " ",
strfmt(getsol(getend(taskP(i))),2), " ",
if(getsol(ontime(i))=1,"yes","no"))
writeln("Number of knights freed on time: ", getsol(totalFreed), "\n")
end-procedure
end-model
|
© 2001-2019 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.