FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

Fantasy OR: Sangraal (CP and MIP models)

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.
  • The MIP model (sangraal.mos) defines binary decision variables x(k,j) indicating whether knight k is the j'th knight to be freed. A formulation alternative uses indicator constraints (sangraalind.mos).
  • The CP model (sangraal_ka.mos or sangraal2_ka.mos) uses the notion of `tasks' with fixed durations and variable start times. These tasks need to be scheduled subject to precedence relations (freeing before preparing) and the disjunctive use of a resource (the hero's time).


Source Files





sangraal_graph.mos

(!******************************************************
   Mosel Example Problems
   ======================

   file sangraal_graph.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. 2022
*******************************************************!)

model Sangraal
 uses "mmxprs", "mmsvg"

 forward 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

 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

Back to examples browserPrevious exampleNext example