(!****************************************************** 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,129/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