(!****************************************************** 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,129/ited.4.3.66 (c) 2008 Fair Isaac Corporation author: S. Heipcke, 2005, rev. Mar. 2022 *******************************************************!) model Sangraal uses "mmxprs", "mmjobs" 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 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_HEUREMPHASIS", 0) ! setparam("XPRS_CUTSTRATEGY", 0) ! setparam("XPRS_PRESOLVE", 0) setcallback(XPRS_CB_INTSOL,->print_solution) maximize(TotalFreed) !******************************************************************** 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