FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home

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_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
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