| 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. Sep. 2018
*****************************************************************!)
model "User branching"
uses "kalis"
parameters
ALG=1
end-parameters
forward public function varchoice(Vars: cpvarlist): integer
forward public function varchoice2(Vars: cpvarlist): integer
forward public function valchoice(x: cpvar): integer
forward public 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
public 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)
public 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)
public 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)
public 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. Sep. 2018
*****************************************************************!)
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 public 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 ****
public 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. Apr. 2019
*****************************************************************!)
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 public 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 ****
public 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
*****************************************************************!)
model "Disjunctive scheduling with probe_settle_disjunction"
uses "kalis"
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
Disj: set of cpctr ! Disjunctions
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("[", start(t).sol, "==>",
start(t).sol + DUR(t), "]:\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. 2007
*****************************************************************!)
model "Disjunctive scheduling with settle_disjunction"
uses "kalis"
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
Disj: set of cpctr ! Disjunctions
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("[", getsol(start(t)), "==>",
getsol(start(t)) + DUR(t), "]:\t ",
getsol(tardiness(t)), " (", getsol(tmp(t)), ")")
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. 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
|
|
