| branching.mos |
(!****************************************************************
CP example problems
===================
file branching.mos
``````````````````
User branching variable and value choice.
The model parameter `ALG' selects one of the predefined
branching strategies.
(c) 2008 Artelys S.A. and Fair Isaac Corporation
Creation: 2005, rev. 2007, rev. Jul. 2022
*****************************************************************!)
model "User branching"
uses "kalis"
parameters
ALG=1
end-parameters
forward function varchoice(Vars: cpvarlist): integer
forward function varchoice2(Vars: cpvarlist): integer
forward function valchoice(x: cpvar): integer
forward function valchoice2(x: cpvar): integer
setparam("KALIS_DEFAULT_LB", 0);
setparam("KALIS_DEFAULT_UB", 20)
declarations
R = 1..10
y: array(R) of cpvar
C: array(R) of integer
Strategy: array(range) of cpbranching
end-declarations
C:: [4, 7, 2, 6, 9, 0,-1, 3, 8,-2]
all_different(y)
forall(i in R | isodd(i)) y(i) >= y(i+1) + 1
y(4) + y(1) = 13; y(8) <= 15; y(7) <> 5
! Definition of user branching strategies:
Strategy(1):= assign_and_forbid(->varchoice2, ->valchoice, y)
Strategy(2):= assign_var(->varchoice, ->valchoice, y)
Strategy(3):= split_domain(->varchoice, ->valchoice2, y, true, 2)
Strategy(4):= split_domain(->varchoice2, ->valchoice, y, false, 5)
! Select a branching strategy
cp_set_branching(Strategy(ALG))
if cp_find_next_sol then
forall(i in R) write(getsol(y(i)), " ")
writeln
end-if
!---------------------------------------------------------------
! **** Variable choice ****
! **** Choose variable with largest degree + smallest domain
function varchoice(Vars: cpvarlist): integer
declarations
Vset,Iset: set of integer
end-declarations
! Get the number of elements of "Vars"
listsize:= getsize(Vars)
! Set on uninstantiated variables
forall(i in 1..listsize)
if not is_fixed(getvar(Vars,i)) then Vset+= {i}; end-if
if Vset={} then
returned:= 0
else
! Get the variables with max. degree
dmax:= max(i in Vset) getdegree(getvar(Vars,i))
forall(i in Vset)
if getdegree(getvar(Vars,i)) = dmax then Iset+= {i}; end-if
dsize:= MAX_INT
! Choose var. with smallest domain among those indexed by 'Iset'
forall(i in Iset)
if getsize(getvar(Vars,i)) < dsize then
returned:= i
dsize:= getsize(getvar(Vars,i))
end-if
end-if
writeln(returned)
end-function
! **** Choose variable y(i) with smallest value of C(i)
function varchoice2(Vars: cpvarlist): integer
declarations
Vset,Iset: set of integer
VarInd: array(Iset) of integer
end-declarations
! Set on uninstantiated variables
listsize:= getsize(Vars)
forall(i in 1..listsize)
if not is_fixed(getvar(Vars,i)) then Vset+= {i}; end-if
if getsize(Vset)=0 then
returned:= 0
else
! Establish a correspondence of indices between 'Vars' and 'y'
forall(i in R)
forall(j in Vset)
if is_same(getvar(Vars,j), y(i)) then
VarInd(i):= j
Vset -= {j}
break 1
end-if
! Choose the variable
imin:= min(i in Iset) i; cmin:= C(imin)
forall(i in Iset)
if C(i) < cmin then
imin:= i; cmin:= C(i)
end-if
returned:= VarInd(imin)
end-if
writeln(imin, " ", returned)
end-function
!---------------------------------------------------------------
! *** Value choice ****
! **** Choose the next value one third larger than lower bound
! (Strategy may be used with any branching scheme since it
! makes sure that the chosen value lies in the domain)
function valchoice(x: cpvar): integer
! returned:= getlb(x)
returned:= getnext(x, getlb(x) + round((getub(x)-getlb(x))/3))
writeln("Value: ", returned, " ", contains(x,returned),
" x: ", x)
end-function
! **** Split the domain into lower third and upper two thirds
! (Strategy to be used only with 'split_domain' branching since
! the chosen value may not be in the domain)
function valchoice2(x: cpvar): integer
returned:= getlb(x) + round((getub(x)-getlb(x))/3)
writeln("Value: ", returned, " x: ", x)
end-function
end-model
|
|
| probeac2001.mos |
(!****************************************************************
CP example problems
===================
file probeac2001.mos
````````````````````
Euler knight tour problem implemented with user-defined
binary constraints.
*** This model cannot be run with a Community Licence
for the default data instance ***
(c) 2008 Artelys S.A. and Fair Isaac Corporation
Creation: 2005, rev. Jul. 2022
*****************************************************************!)
model "Euler Knight Moves"
uses "kalis"
parameters
S = 8 ! No. of rows/columns
end-parameters
N:= S * S ! Total number of cells
setparam("KALIS_DEFAULT_LB", 0)
setparam("KALIS_DEFAULT_UB", N-1)
forward function valid_knight_move(a:integer, b:integer): boolean
declarations
PATH = 1..N ! Cells on the board
pos: array(PATH) of cpvar ! Position p in tour
end-declarations
! Setting names of decision variables
forall(i in PATH) setname(pos(i), "Position"+i)
! Fix the start position
pos(1) = 0
! Each cell is visited once
all_different(pos, KALIS_GEN_ARC_CONSISTENCY)
! The knight's path obeys the chess rules for valid knight moves
forall(i in 1..N-1)
generic_binary_constraint(pos(i), pos(i+1), ->valid_knight_move)
generic_binary_constraint(pos(N), pos(1), ->valid_knight_move)
! Setting enumeration parameters
cp_set_branching(probe_assign_var(KALIS_SMALLEST_MIN,
KALIS_MAX_TO_MIN, pos, 14))
! Search for up to NBSOL solutions
solct:= 0
if not cp_find_next_sol then
writeln("No solution")
else
writeln(pos)
end-if
! **** Test whether the move from a to b is admissible ****
function valid_knight_move(a:integer, b:integer): boolean
declarations
xa,ya,xb,yb,delta_x,delta_y: integer
end-declarations
xa := a div S
ya := a mod S
xb := b div S
yb := b mod S
delta_x := abs(xa-xb)
delta_y := abs(ya-yb)
returned := (delta_x<=2) and (delta_y<=2) and (delta_x+delta_y=3)
end-function
end-model
|
|
| probeac2001_nary.mos |
(!****************************************************************
CP example problems
===================
file probeac2001_nary.mos
`````````````````````````
Euler knight tour problem implemented with user-defined
binary constraints.
-- n-ary formulation version --
*** This model cannot be run with a Community Licence
for the default data instance ***
(c) 2008 Artelys S.A. and Fair Isaac Corporation
Creation: May 2005, rev. Jul. 2022
*****************************************************************!)
model "Euler Knight Moves"
uses "kalis"
parameters
S = 8 ! No. of rows/columns
end-parameters
N:= S * S ! Total number of cells
setparam("KALIS_DEFAULT_LB", 0)
setparam("KALIS_DEFAULT_UB", N-1)
forward function valid_knight_move(vals: cptuple, s: integer): boolean
declarations
PATH = 1..N ! Cells on the board
pos: array(PATH) of cpvar ! Position p in tour
propagation : integer ! Alg choice: 0, 1, or 2
end-declarations
! Selecting the propagation algorithm for the generic nary constraint
propagation := 0
! Setting names of decision variables
forall(i in PATH) setname(pos(i), "Position"+i)
! Fix the start position
pos(1) = 0
! Each cell is visited once
all_different(pos, KALIS_GEN_ARC_CONSISTENCY)
! The knight's path obeys the chess rules for valid knight moves
forall(i in 1..N-1)
generic_nary_constraint({pos(i), pos(i+1)}, ->valid_knight_move,propagation,S)
generic_nary_constraint({pos(N), pos(1)}, ->valid_knight_move,propagation,S)
! Setting enumeration parameters
cp_set_branching(probe_assign_var(KALIS_SMALLEST_MIN,
KALIS_MAX_TO_MIN, pos, 14))
! Search for up to NBSOL solutions
solct:= 0
if not cp_find_next_sol then
writeln("No solution")
else
writeln(pos)
end-if
! **** Test whether the move from a to b is admissible ****
function valid_knight_move(vals: cptuple, s: integer): boolean
declarations
xa,ya,xb,yb,delta_x,delta_y: integer
a,b : integer
end-declarations
! Current position data
a := getelt(vals,1) ! 1 : pos(i)
b := getelt(vals,2) ! 2 : pos(i+1)
xa := a div s
ya := a mod s
xb := b div s
yb := b mod s
delta_x := abs(xa-xb)
delta_y := abs(ya-yb)
returned := (delta_x<=2) and (delta_y<=2) and (delta_x+delta_y=3)
end-function
end-model
|
|
| probesettledisjunction.mos |
(!****************************************************************
CP example problems
===================
file probesettledisjunction.mos
```````````````````````````````
Scheduling disjunctive tasks with a probe-settle-disjunctions strategy.
(c) 2008 Artelys S.A. and Fair Isaac Corporation
rev. Apr. 2022
*****************************************************************!)
model "Disjunctive scheduling with probe_settle_disjunction"
uses "kalis", "mmsystem"
declarations
NBTASKS = 5
TASKS = 1..NBTASKS ! Set of tasks
DUR: array(TASKS) of integer ! Task durations
DUE: array(TASKS) of integer ! Due dates
WEIGHT: array(TASKS) of integer ! Weights of tasks
start: array(TASKS) of cpvar ! Start times
tmp: array(TASKS) of cpvar ! Aux. variable
tardiness: array(TASKS) of cpvar ! Tardiness
twt: cpvar ! Objective variable
zeroVar: cpvar ! 0-valued variable
Strategy: array(range) of cpbranching ! Branching strategy
end-declarations
DUR :: [21,53,95,55,34]
DUE :: [66,101,232,125,150]
WEIGHT :: [1,1,1,1,1]
setname(twt, "Total weighted tardiness")
zeroVar = 0
setname(zeroVar, "zeroVar")
forall(t in TASKS) do
start(t) >= 0
start(t).name:= "Start("+t+")"
tmp(t) = start(t) + DUR(t) - DUE(t)
tardiness(t).name:= "Tard("+t+")"
tardiness(t) = maximum({tmp(t),zeroVar})
end-do
twt = sum(t in TASKS) (WEIGHT(t) * tardiness(t))
! Create the disjunctive constraints
forall(t in 1..NBTASKS-1, s in t+1..NBTASKS)
(start(t) + DUR(t) <= start(s)) or
(start(s) + DUR(s) <= start(t))
! Define the branching strategy
Strategy(1):= probe_settle_disjunction(1)
Strategy(2):= split_domain(KALIS_LARGEST_MIN,KALIS_MIN_TO_MAX)
cp_set_branching(Strategy)
! Solve the problem
if not cp_minimize(twt) then
writeln("problem is inconsistent")
exit(0)
end-if
forall(t in TASKS)
writeln(formattext("[%3d==>%3d]:\t %2d (%d)", start(t).sol,
start(t).sol + DUR(t), tardiness(t).sol, tmp(t).sol))
writeln("Total weighted tardiness: ", twt.sol)
end-model
|
|
| settledisjunction.mos |
(!****************************************************************
CP example problems
===================
file settledisjunction.mos
``````````````````````````
Scheduling disjunctive tasks.
(c) 2008 Artelys S.A. and Fair Isaac Corporation
Creation: 2005, rev. Apr. 2022
*****************************************************************!)
model "Disjunctive scheduling with settle_disjunction"
uses "kalis", "mmsystem"
declarations
NBTASKS = 5
TASKS = 1..NBTASKS ! Set of tasks
DUR: array(TASKS) of integer ! Task durations
DUE: array(TASKS) of integer ! Due dates
WEIGHT: array(TASKS) of integer ! Weights of tasks
start: array(TASKS) of cpvar ! Start times
tmp: array(TASKS) of cpvar ! Aux. variable
tardiness: array(TASKS) of cpvar ! Tardiness
twt: cpvar ! Objective variable
zeroVar: cpvar ! 0-valued variable
Strategy: array(range) of cpbranching ! Branching strategy
end-declarations
DUR :: [21,53,95,55,34]
DUE :: [66,101,232,125,150]
WEIGHT :: [1,1,1,1,1]
setname(twt, "Total weighted tardiness")
zeroVar = 0
setname(zeroVar, "zeroVar")
forall (t in TASKS) do
start(t) >= 0
setname(start(t), "Start("+t+")")
tmp(t) = start(t) + DUR(t) - DUE(t)
setname(tardiness(t), "Tard("+t+")")
tardiness(t) = maximum({tmp(t),zeroVar})
end-do
twt = sum(t in TASKS) (WEIGHT(t) * tardiness(t))
! Create the disjunctive constraints
forall(t in 1..NBTASKS-1, s in t+1..NBTASKS)
(start(t) + DUR(t) <= start(s)) or
(start(s) + DUR(s) <= start(t))
! Define the branching strategy
Strategy(1):= settle_disjunction
Strategy(2):= split_domain(KALIS_LARGEST_MIN,KALIS_MIN_TO_MAX)
cp_set_branching(Strategy)
! Solve the problem
if not(cp_minimize(twt)) then
writeln("Problem is inconsistent")
exit(0)
end-if
forall (t in TASKS)
writeln(formattext("[%3d==>%3d]:\t %2d (%d)",start(t).sol,
start(t).sol + DUR(t), tardiness(t).sol, tmp(t).sol))
writeln("Total weighted tardiness: ", getsol(twt))
end-model
|
|
| taskserializer.mos |
(!****************************************************************
CP example problems
===================
file taskserializer.mos
```````````````````````
Resource-constrained project planning problem (construction of
a house) modeled with task and resource objects.
- Defining a task-based branching strategy -
*** This model cannot be run with a Community Licence ***
(c) 2008 Artelys S.A. and Fair Isaac Corporation
rev. Apr. 2022
*****************************************************************!)
model "Tasks serialization example"
uses "kalis"
declarations
Masonry, Carpentry, Roofing, Windows, Facade, Garden, Plumbing,
Ceiling, Painting, MovingIn : cptask ! Declaration of tasks
Taskset : set of cptask
money_available : cpresource ! Resource declaration
end-declarations
forward function selectNextTask(tasks: cptasklist) : integer
! 'money_available' is a cumulative resource with max. amount of 29$
set_resource_attributes(money_available,KALIS_DISCRETE_RESOURCE,29)
! Limit resource availability to 20$ in the time interval [0,14]
setcapacity(money_available, 0, 14, 20)
! Setting the task durations and predecessor sets
set_task_attributes(Masonry , 7)
set_task_attributes(Carpentry, 3, {Masonry})
set_task_attributes(Roofing , 1, {Carpentry})
set_task_attributes(Windows , 1, {Roofing})
set_task_attributes(Facade , 2, {Roofing})
set_task_attributes(Garden , 1, {Roofing})
set_task_attributes(Plumbing , 8, {Masonry})
set_task_attributes(Ceiling , 3, {Masonry})
set_task_attributes(Painting , 2, {Ceiling})
set_task_attributes(MovingIn , 1, {Windows,Facade,Garden,Painting})
! Setting the resource consumptions
consumes(Masonry , 7, money_available)
consumes(Carpentry, 3, money_available)
consumes(Roofing , 1, money_available)
consumes(Windows , 1, money_available)
consumes(Facade , 2, money_available)
consumes(Garden , 1, money_available)
consumes(Plumbing , 8, money_available)
consumes(Ceiling , 3, money_available)
consumes(Painting , 2, money_available)
consumes(MovingIn , 1, money_available)
! Set of tasks to schedule
Taskset := {Masonry, Carpentry, Roofing, Windows, Facade, Garden,
Plumbing, Ceiling, Painting, MovingIn}
! Set the custom branching strategy using task_serialize:
! - the task serialization process will use the function
! "selectNextTask" to look for the next task to fix
! - it will use the "KALIS_MAX_TO_MIN" value selection heuristic
! to set the tasks duration variable
! - and the "KALIS_MIN_TO_MAX" value selection heuristic to set
! the start of the task
cp_set_branching(task_serialize(->selectNextTask,
KALIS_MAX_TO_MIN, KALIS_MIN_TO_MAX, Taskset))
! Find the optimal schedule (minimizing the makespan)
if 0 <> cp_schedule(getmakespan) then
cp_show_sol
else
writeln("No solution found")
end-if
!-------------------------------------------------------------
! **** Function to select the next task to schedule
function selectNextTask(tasks: cptasklist) : integer
write("selectNextTask : ")
declarations
Vset,Iset: set of integer
end-declarations
! Get the number of elements of "tasks"
listsize:= getsize(tasks)
! Set of uninstantiated variables
forall(i in 1..listsize)
if not is_fixed(getstart(gettask(tasks,i))) or
not is_fixed(getduration(gettask(tasks,i))) then
Vset+= {i};
end-if
if Vset={} then
returned:= 0
else
! Get the variables with max. degree
dmax:= max(i in Vset) getsize(getduration(gettask(tasks,i)))
forall(i in Vset)
if getsize(getduration(gettask(tasks,i))) = dmax then
Iset+= {i}; end-if
dsize:= MAX_INT
! Choose var. with smallest domain among those indexed by 'Iset'
forall(i in Iset)
if getsize(getstart(gettask(tasks,i))) < dsize then
returned:= i
dsize:= getsize(getstart(gettask(tasks,i)))
end-if
end-if
if returned <> 0 then
writeln(gettask(tasks,returned))
end-if
end-function
end-model
|
|
| taskserializer2.mos |
(!****************************************************************
CP example problems
===================
file taskserializer2.mos
````````````````````````
Resource-constrained project planning problem (construction of
a house) modeled with task and resource objects.
- Defining a task-based branching strategy -
- Specifying callback routines by name -
*** This model cannot be run with a Community Licence ***
(c) 2008 Artelys S.A. and Fair Isaac Corporation
rev. Sep. 2018
*****************************************************************!)
model "Tasks serialization example"
uses "kalis"
declarations
Masonry, Carpentry, Roofing, Windows, Facade, Garden, Plumbing,
Ceiling, Painting, MovingIn : cptask ! Declaration of tasks
Taskset : set of cptask
money_available : cpresource ! Resource declaration
end-declarations
forward public function selectNextTask(tasks: cptasklist) : integer
! 'money_available' is a cumulative resource with max. amount of 29$
set_resource_attributes(money_available,KALIS_DISCRETE_RESOURCE,29)
! Limit resource availability to 20$ in the time interval [0,14]
setcapacity(money_available, 0, 14, 20)
! Setting the task durations and predecessor sets
set_task_attributes(Masonry , 7)
set_task_attributes(Carpentry, 3, {Masonry})
set_task_attributes(Roofing , 1, {Carpentry})
set_task_attributes(Windows , 1, {Roofing})
set_task_attributes(Facade , 2, {Roofing})
set_task_attributes(Garden , 1, {Roofing})
set_task_attributes(Plumbing , 8, {Masonry})
set_task_attributes(Ceiling , 3, {Masonry})
set_task_attributes(Painting , 2, {Ceiling})
set_task_attributes(MovingIn , 1, {Windows,Facade,Garden,Painting})
! Setting the resource consumptions
consumes(Masonry , 7, money_available)
consumes(Carpentry, 3, money_available)
consumes(Roofing , 1, money_available)
consumes(Windows , 1, money_available)
consumes(Facade , 2, money_available)
consumes(Garden , 1, money_available)
consumes(Plumbing , 8, money_available)
consumes(Ceiling , 3, money_available)
consumes(Painting , 2, money_available)
consumes(MovingIn , 1, money_available)
! Set of tasks to schedule
Taskset := {Masonry, Carpentry, Roofing, Windows, Facade, Garden,
Plumbing, Ceiling, Painting, MovingIn}
! Set the custom branching strategy using task_serialize:
! - the task serialization process will use the function
! "selectNextTask" to look for the next task to fix
! - it will use the "KALIS_MAX_TO_MIN" value selection heuristic
! to set the tasks duration variable
! - and the "KALIS_MIN_TO_MAX" value selection heuristic to set
! the start of the task
cp_set_branching(task_serialize("selectNextTask",
KALIS_MAX_TO_MIN, KALIS_MIN_TO_MAX, Taskset))
! Find the optimal schedule (minimizing the makespan)
if 0 <> cp_schedule(getmakespan) then
cp_show_sol
else
writeln("No solution found")
end-if
!-------------------------------------------------------------
! **** Function to select the next task to schedule
public function selectNextTask(tasks: cptasklist) : integer
write("selectNextTask : ")
declarations
Vset,Iset: set of integer
end-declarations
! Get the number of elements of "tasks"
listsize:= getsize(tasks)
! Set of uninstantiated variables
forall(i in 1..listsize)
if not is_fixed(getstart(gettask(tasks,i))) or
not is_fixed(getduration(gettask(tasks,i))) then
Vset+= {i};
end-if
if Vset={} then
returned:= 0
else
! Get the variables with max. degree
dmax:= max(i in Vset) getsize(getduration(gettask(tasks,i)))
forall(i in Vset)
if getsize(getduration(gettask(tasks,i))) = dmax then
Iset+= {i}; end-if
dsize:= MAX_INT
! Choose var. with smallest domain among those indexed by 'Iset'
forall(i in Iset)
if getsize(getstart(gettask(tasks,i))) < dsize then
returned:= i
dsize:= getsize(getstart(gettask(tasks,i)))
end-if
end-if
if returned <> 0 then
writeln(gettask(tasks,returned))
end-if
end-function
end-model
|
|
| altresource_scheduling.mos |
(!****************************************************************
CP example problems
===================
file altresource_scheduling.mos
```````````````````````````````
Scheduling jobs with resource choice and variable durations.
Task-based branching strategy with user-defined resource selection.
(c) 2022 Artelys S.A. and Fair Isaac Corporation
Creation: Apr. 2022
*****************************************************************!)
model "Scheduling with alternative resources"
uses "kalis", "mmsystem"
setparam("KALIS_DEFAULT_LB", 0)
setparam("KALIS_VERBOSE_LEVEL", 1)
forward procedure print_and_check_solution
forward public function smallest_duration_assignment(assignments: cpvarlist): integer
declarations
JOBS: set of string ! Index set of jobs
TEAMS: set of string ! Index set of teams (resources)
DURATIONS: array(JOBS, TEAMS) of integer ! Durations of JOBS for each team
POSSIBLE_TEAMS: array(JOBS) of set of string ! Possible team for each task
PRECEDENCES: list of list of string ! Pairs of precedence constraints
job: array(JOBS) of cptask ! Jobs
team: array(TEAMS) of cpresource ! Teams
ASSIGN_VARS_INDEXES: set of integer ! Mapping model entities to indices
ASSIGNMENT_VARS_JOB: array(ASSIGN_VARS_INDEXES) of string
ASSIGNMENT_VARS_TEAM: array(ASSIGN_VARS_INDEXES) of string
end-declarations
! **************** Data ****************
! -1 duration indicates the team cannot process the task
DURATIONS::(["J0", "J1", "J2", "J3", "J4", "J5", "J6", "J7", "J8", "J9",
"J10", "J11", "J12", "J13", "J14", "J15", "J16", "J17"],
["T1", "T2", "T3"])[
2, -1, 2,
16, 14, 15,
9, -1, 8,
8, 5, 8,
10, 11, 8,
6, 5, 7,
-1, 3, 4,
2, 1, 2,
9, 6, 9,
5, 7, -1,
3, -1, 1,
2, 3, 3,
1, -1, 1,
7, 4, 7,
4, 6, 4,
3, 2, 1,
9, 9, -1,
1, 2, 3]
forall(j in JOBS)
POSSIBLE_TEAMS(j) := union(t in TEAMS | DURATIONS(j, t) <> -1) {t}
PRECEDENCES:= [ ["J1", "J0"], ["J2", "J1"], ["J3", "J1"], ["J13", "J1"],
["J4", "J2"], ["J5", "J3"], ["J6", "J3"], ["J8", "J3"],
["J9", "J3"], ["J14", "J3"], ["J5", "J4"], ["J7", "J5"],
["J8", "J5"], ["J10", "J5"], ["J12", "J6"], ["J15", "J7"],
["J11", "J8"], ["J15", "J10"], ["J16", "J11"],
["J14", "J13"], ["J15", "J13"], ["J17", "J16"]]
! **************** Problem formulation ****************
! Define discrete resources
forall(t in TEAMS) do
set_resource_attributes(team(t), KALIS_DISCRETE_RESOURCE, 1)
team(t).name := t
end-do
! Define possible teams for each task
forall(j in JOBS) do
job(j).name := j
requires(job(j), union(t in POSSIBLE_TEAMS(j)) {resusage(team(t), 1)})
end-do
! Define associated duration for each task
forall(j in JOBS) do
setdomain(getduration(job(j)),
min(t in POSSIBLE_TEAMS(j)) DURATIONS(j, t),
max(t in POSSIBLE_TEAMS(j)) DURATIONS(j, t))
forall(t in POSSIBLE_TEAMS(j))
implies(getassignment(job(j), team(t)) = 1,
getduration(job(j)) = DURATIONS(j, t))
end-do
! Define precedences
forall(j in JOBS)
setpredecessors(job(j), union(p in PRECEDENCES | p(1) = j) {job(p.last)})
cp_close_schedule
! **************** Solving ****************
! Perform constraint propagation
if not cp_propagate then
writeln("Problem is infeasible")
exit(1)
end-if
! Initialize mapping with assignment variables
forall(j in JOBS, t in POSSIBLE_TEAMS(j)) do
var_index := getindex(getassignment(job(j), team(t)))
ASSIGN_VARS_INDEXES += {var_index}
ASSIGNMENT_VARS_JOB(var_index) := j
ASSIGNMENT_VARS_TEAM(var_index) := t
end-do
! Define branching strategy with user-defined resource selection criterion
Strategy:= task_serialize(KALIS_SMALLEST_EST, KALIS_MIN_TO_MAX,
KALIS_MIN_TO_MAX, "smallest_duration_assignment", KALIS_MAX_TO_MIN,
job, MAX_INT, 1)
cp_set_schedule_strategy(KALIS_INITIAL_SOLUTION, Strategy)
cp_set_schedule_strategy(KALIS_OPTIMAL_SOLUTION, Strategy)
setparam("KALIS_MAX_COMPUTATION_TIME", 10)
! Solve the problem
if cp_schedule(getmakespan)=0 then
writeln("No solution")
exit(0)
end-if
! Solution printing
print_and_check_solution
! **************** Subroutine definitions ****************
procedure print_and_check_solution
declarations
starts: array(JOBS) of integer
ends: array(JOBS) of integer
operating_teams: array(JOBS) of string
end-declarations
! Display the solution
writeln("makespan=", getsol(getmakespan))
forall(j in JOBS) do
starts(j) := getsol(getstart(job(j)))
ends(j) := getsol(getend(job(j)))
forall(t in POSSIBLE_TEAMS(j) | getsol(getassignment(job(j),team(t))) > 0) do
operating_teams(j) := t
break
end-do
writeln(formattext("%3s: %2d - %2d team=%s", j, starts(j), ends(j),
operating_teams(j)))
end-do
! Check solution
forall(j in JOBS | operating_teams(j) not in TEAMS)
writeln("Error: ", j, " doesn't have an operating team.")
forall(p in PRECEDENCES | starts(getfirst(p)) < ends(getlast(p)))
writeln("Error: Precedence constraint ", p, " is violated.")
forall(j in JOBS | starts(j) + DURATIONS(j, operating_teams(j)) <> ends(j))
writeln("Error: Job ", j, " has a wrong duration.")
if max(j in JOBS) ends(j) <> getsol(getmakespan) then
writeln("Error: Objective value is different from computed makespan value.")
end-if
end-procedure
! **** User-defined resource assignment strategy
public function smallest_duration_assignment(assignments: cpvarlist): integer
min_duration := MAX_INT
returned := 0 ! Selected variable index value
forall(i in 1..getsize(assignments)) do
if is_fixed(getvar(assignments, i)) then
next
end-if
var_index := getindex(getvar(assignments, i))
if var_index not in ASSIGN_VARS_INDEXES then
next
end-if
j := ASSIGNMENT_VARS_JOB(var_index)
t := ASSIGNMENT_VARS_TEAM(var_index)
if DURATIONS(j, t) < min_duration then
returned := i
min_duration := DURATIONS(j, t)
end-if
end-do
end-function
end-model
|
|
| altresource_scheduling_softbreaks.mos |
(!****************************************************************
CP example problems
===================
file altresource_scheduling_softbreaks.mos
``````````````````````````````````````````
Scheduling jobs with resource choice and variable durations.
Additional soft breaks (pre-emptive breaks) on resources taken into account.
(c) 2022 Artelys S.A. and Fair Isaac Corporation
Creation: Apr. 2022
*****************************************************************!)
model "Scheduling with alternative resources"
uses "kalis", "mmsystem"
setparam("KALIS_DEFAULT_LB", 0)
setparam("KALIS_VERBOSE_LEVEL", 1)
declarations
JOBS: set of string ! Index set of jobs
TEAMS: set of string ! Index set of teams (resources)
DURATIONS: array(JOBS, TEAMS) of integer ! Durations of JOBS for each team
POSSIBLE_TEAMS: array(JOBS) of set of string ! Possible team for each task
PRECEDENCES: list of list of string ! Pairs of precedence constraints
SOFT_BREAKS: array(TEAMS) of list of list of integer ! Start and end times
! of soft breaks for each team
ALLOW_START_IN_IDLE: boolean
job: array(JOBS) of cptask ! Jobs
team: array(TEAMS) of cpresource ! Teams
procedure print_and_check_solution
function get_actual_duration(j: string, t: string, start: integer): integer
end-declarations
! **************** Data ****************
! -1 duration indicates the team cannot process the task
DURATIONS::(["J0", "J1", "J2", "J3", "J4", "J5", "J6", "J7", "J8", "J9",
"J10", "J11", "J12", "J13", "J14", "J15", "J16", "J17"],
["T1", "T2", "T3"])[
2, -1, 2,
16, 14, 15,
9, -1, 8,
8, 5, 8,
10, 11, 8,
6, 5, 7,
-1, 3, 4,
2, 1, 2,
9, 6, 9,
5, 7, -1,
3, -1, 1,
2, 3, 3,
1, -1, 1,
7, 4, 7,
4, 6, 4,
3, 2, 1,
9, 9, -1,
1, 2, 3]
forall(j in JOBS)
POSSIBLE_TEAMS(j) := union(t in TEAMS | DURATIONS(j, t) <> -1) {t}
PRECEDENCES:= [ ["J1", "J0"], ["J2", "J1"], ["J3", "J1"], ["J13", "J1"],
["J4", "J2"], ["J5", "J3"], ["J6", "J3"], ["J8", "J3"],
["J9", "J3"], ["J14", "J3"], ["J5", "J4"], ["J7", "J5"],
["J8", "J5"], ["J10", "J5"], ["J12", "J6"], ["J15", "J7"],
["J11", "J8"], ["J15", "J10"], ["J16", "J11"],
["J14", "J13"], ["J15", "J13"], ["J17", "J16"]]
SOFT_BREAKS::(["T1", "T2", "T3"]) [[[10, 25], [42, 52]], [[15, 37]],
[[25, 35], [45, 58]]]
ALLOW_START_IN_IDLE := true
! **************** Problem formulation ****************
! Define discrete resources
forall(t in TEAMS) do
set_resource_attributes(team(t), KALIS_DISCRETE_RESOURCE, 1)
team(t).name := t
end-do
! Define possible teams for each task
forall(j in JOBS) do
job(j).name := j
requires(job(j), union(t in POSSIBLE_TEAMS(j)) {resusage(team(t), 1)})
end-do
! Define associated duration for each task
forall(j in JOBS) do
! Initialize duration bounds
setdomain(getduration(job(j)),
min(t in POSSIBLE_TEAMS(j)) DURATIONS(j, t),
max(t in POSSIBLE_TEAMS(j)) DURATIONS(j, t))
forall(t in POSSIBLE_TEAMS(j)) do
! Set nominal duration
setduration(team(t), job(j), DURATIONS(j, t))
! Update the actual duration with idle times
forall(b in SOFT_BREAKS(t))
update_duration_with_idle_times(team(t), job(j), b.first, b.last,
ALLOW_START_IN_IDLE)
end-do
end-do
! Display all constraints involving the duration of task 'J0'
cp_show_var_constraints(getduration(job("J0")))
! Define precedences
forall(j in JOBS)
setpredecessors(job(j), union(p in PRECEDENCES | p(1) = j) {job(p.last)})
cp_close_schedule
! **************** Solving ****************
! Perform constraint propagation
if not cp_propagate then
writeln("Problem is infeasible")
exit(1)
end-if
setparam("KALIS_MAX_COMPUTATION_TIME", 10)
! Solve the problem
if cp_schedule(getmakespan)=0 then
writeln("No solution")
exit(0)
end-if
! Solution printing
print_and_check_solution
! **************** Subroutine definitions ****************
procedure print_and_check_solution
declarations
starts: array(JOBS) of integer
ends: array(JOBS) of integer
operating_teams: array(JOBS) of string
end-declarations
! Display the solution
writeln("makespan=", getsol(getmakespan))
forall(j in JOBS) do
starts(j) := getsol(getstart(job(j)))
ends(j) := getsol(getend(job(j)))
forall(t in POSSIBLE_TEAMS(j) | getsol(getassignment(job(j),team(t)))>0) do
operating_teams(j) := t
break
end-do
writeln(formattext("%3s: %2d - %2d team=%s", j, starts(j), ends(j),
operating_teams(j)))
end-do
! Check solution
forall(j in JOBS | operating_teams(j) not in TEAMS)
writeln("Error: ", j, " doesn't have an operating team.")
forall(p in PRECEDENCES | starts(getfirst(p)) < ends(getlast(p)))
writeln("Error: Precedence constraint ", p, " is violated.")
forall(j in JOBS | starts(j) + get_actual_duration(j, operating_teams(j),
starts(j)) <> ends(j))
writeln("Error: Job ", j, " has a wrong duration.")
if max(j in JOBS) ends(j) <> getsol(getmakespan) then
writeln("Error: Objective value is different from computed makespan value.")
end-if
end-procedure
! **** Return the actual duration of a job given its team and start
function get_actual_duration(j: string, t: string, start: integer): integer
expected_end := start + DURATIONS(j, t)
forall(b in SOFT_BREAKS(t)) do
if start >= b.last then
next
end-if
! Adding soft break duration
if expected_end > b.first then
expected_end += b.last - maxlist(start, b.first)
end-if
end-do
returned := expected_end - start
end-function
end-model
|
|
| groupserializer.mos |
(!****************************************************************
CP example problems
===================
file groupserializer.mos
````````````````````````
Resource-constrained project planning problem (construction of
a house) modeled with task and resource objects.
- Defining a group serializer branching strategy -
*** This model cannot be run with a Community Licence ***
(c) 2021 Artelys S.A. and Fair Isaac Corporation
rev. Apr. 2022
*****************************************************************!)
model "Groups serialization example"
uses "kalis"
declarations
Masonry, Carpentry, Roofing, Windows, Facade, Garden, Plumbing,
Ceiling, Painting, MovingIn : cptask ! Declaration of tasks
Taskset : set of cptask
money_available : cpresource ! Resource declaration
! Branching strategy
Strategy: cpbranching
TaskBranching: dynamic array(string) of set of cpbranching
TaskGroups: set of cpbsgroup
TaskTag: dynamic array(range) of string
end-declarations
forward public function select_task_group(glist: cpbsgroup): real
! 'money_available' is a cumulative resource with max. amount of 29$
set_resource_attributes(money_available,KALIS_DISCRETE_RESOURCE,29)
! Limit resource availability to 20$ in the time interval [0,14]
setcapacity(money_available, 0, 14, 20)
! Setting task name
Masonry.name := "Masonry"
Carpentry.name := "Carpentry"
Roofing.name := "Roofing"
Windows.name := "Windows"
Facade.name := "Facade"
Garden.name := "Garden"
Plumbing.name := "Plumbing"
Ceiling.name := "Ceiling"
Painting.name := "Painting"
MovingIn.name := "MovingIn"
! Setting the task durations and predecessor sets
set_task_attributes(Masonry , 7)
set_task_attributes(Carpentry, 3, {Masonry})
set_task_attributes(Roofing , 1, {Carpentry})
set_task_attributes(Windows , 1, {Roofing})
set_task_attributes(Facade , 2, {Roofing})
set_task_attributes(Garden , 1, {Roofing})
set_task_attributes(Plumbing , 8, {Masonry})
set_task_attributes(Ceiling , 3, {Masonry})
set_task_attributes(Painting , 2, {Ceiling})
set_task_attributes(MovingIn , 1, {Windows,Facade,Garden,Painting})
! Setting the resource consumptions
consumes(Masonry , 7, money_available)
consumes(Carpentry, 3, money_available)
consumes(Roofing , 1, money_available)
consumes(Windows , 1, money_available)
consumes(Facade , 2, money_available)
consumes(Garden , 1, money_available)
consumes(Plumbing , 8, money_available)
consumes(Ceiling , 3, money_available)
consumes(Painting , 2, money_available)
consumes(MovingIn , 1, money_available)
! Set of tasks to schedule
Taskset := {Masonry, Carpentry, Roofing, Windows, Facade, Garden,
Plumbing, Ceiling, Painting, MovingIn}
! Set the custom branching strategy using group_serializer:
! - the group serialization process will use the function
! "select_task_group" to look for the next group to set
! - this function will score each group and the group with the best score is
! selected next
! - the "KALIS_MAX_TO_MIN" value selection heuristic is used to choose values
! for the tasks duration variable
! - and the "KALIS_MIN_TO_MAX" value selection heuristic is applied for
! the start of the task
! - group serializer gives the user a high level of refinement within the
! definition of the search strategy
cnt_task := 1
forall(task in Taskset) do
TaskBranching(task.name) +=
{assign_var(KALIS_SMALLEST_DOMAIN, KALIS_MIN_TO_MAX, {getstart(task)})}
TaskBranching(task.name) +=
{assign_var(KALIS_SMALLEST_DOMAIN, KALIS_MAX_TO_MIN, {getduration(task)})}
TaskBranching(task.name) +=
{assign_var(KALIS_SMALLEST_DOMAIN, KALIS_MAX_TO_MIN,
{getconsumption(task, money_available)})}
TaskGroups += {bs_group(TaskBranching(task.name), cnt_task)}
TaskTag(cnt_task) := task.name
cnt_task += 1
end-do
Strategy := group_serializer(TaskGroups, "select_task_group")
cp_set_schedule_strategy(KALIS_INITIAL_SOLUTION, Strategy)
! Find the optimal schedule (minimizing the makespan)
if 0 <> cp_schedule(getmakespan) then
cp_show_sol
else
writeln("No solution found")
end-if
!-------------------------------------------------------------
! **** Function to select the next group to branch on
! Each group will be scored and the group with the best score will be picked
! as the next group
public function select_task_group(glist: cpbsgroup): real
! Retrieve task from tag
tag := gettag(glist)
! Initializing score value
returned := 0.0
! Build score value as a combination of 1/ max degree and 2/ smallest domain
forall(task in Taskset | TaskTag(tag) = task.name) do
returned += 100 * getsize(getduration(task))
returned -= getsize(getstart(task))
end-do
end-function
end-model
|
|
