(!****************************************************************
CP example problems
===================
file solution.mos
`````````````````
Using callbacks to output the search tree.
(c) 2008 Artelys S.A. and Fair Isaac Corporation
Creation: 2005, rev. 2007
*****************************************************************!)
model "Using callbacks"
uses "kalis"
declarations
NBTASKS = 5
TASKS = 1..NBTASKS ! Set of tasks
DUR: array(TASKS) of integer ! Task durations
DURs: array(set of cpvar) of integer ! 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
nodesx: array(range) of integer ! x-coordinates
nodesy: array(range) of integer ! y-coordinates
currentpos: integer
end-declarations
! Initialization of search tree data
nodesx(0) := 1
nodesy(0) := 0
currentpos := 1
! **********************************************************
! solution_found: called each time a solution is found
! **********************************************************
procedure solution_found
writeln("A solution has been found :")
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-procedure
! **********************************************************
! node_explored: called each time a node is explored
! **********************************************************
procedure node_explored
nodesx(currentpos) += 1
if (nodesx(currentpos-1)>nodesx(currentpos)) then
nodesx(currentpos) := nodesx(currentpos-1)
end-if
nodesy(currentpos) := -currentpos
writeln("[Node explored depth : " , (-nodesy(currentpos)), "]")
end-procedure
! **********************************************************
! go_down_branch: called each time the search goes down
! a branch of the search tree
! **********************************************************
procedure go_down_branch
writeln("[Branch go_down " , (-nodesy(currentpos)) , "]")
currentpos := currentpos + 1
end-procedure
! **********************************************************
! go_up_branch: called each time the search goes up
! a branch of the search tree
! **********************************************************
procedure go_up_branch
currentpos := currentpos - 1
writeln("[Branch go_up " , (-nodesy(currentpos)) , "]")
end-procedure
! **********************************************************
! Problem definition
! **********************************************************
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")
! Setting up the decision variables
forall (t in TASKS) do
start(t) >= 0
setname(start(t), "Start("+t+")")
DURs(start(t)):= DUR(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
disjunctive(union(t in TASKS) {start(t)}, DURs, Disj, 1)
! The setxxxcallback methods must be called before
! setting the branching with 'cp_set_branching'
cp_set_solution_callback("solution_found")
cp_set_node_callback("node_explored")
cp_set_branch_callback("go_down_branch", "go_up_branch")
Strategy(0):= settle_disjunction
Strategy(1):= split_domain(KALIS_MAX_DEGREE,KALIS_MIN_TO_MAX)
cp_set_branching(Strategy)
if not(cp_minimize(twt)) then
writeln("problem is inconsistent")
exit(0)
end-if
end-model
|
(!****************************************************************
CP example problems
===================
file solution_graph.mos
```````````````````````
Using callbacks to draw a user graph.
(c) 2008 Artelys S.A. and Fair Isaac Corporation
Creation: 2005, rev. Sep. 2007
*****************************************************************!)
model "Using callbacks"
uses "kalis", "mmsvg"
declarations
NBTASKS = 5
TASKS = 1..NBTASKS ! Set of tasks
DUR: array(TASKS) of integer ! Task durations
DURs: array(set of cpvar) of integer ! 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
nodesx: array(range) of integer ! x-coordinates
nodesy: array(range) of integer ! y-coordinates
currentpos: integer
end-declarations
! Initialization of user graph
svgaddgroup("DownGraph", "Down branch", SVG_BLUE)
svgsetstyle(SVG_STROKEOPACITY,0.75)
svgaddgroup("UpGraph", "Up branch", SVG_RED)
svgsetstyle(SVG_STROKEOPACITY,0.75)
svgaddgroup("SolGraph", "Solution", SVG_GREEN)
svgsetstyle(SVG_FONTSIZE,"6px")
svgsetstyle(SVG_STROKEWIDTH,0.5)
svgsetgraphscale(20)
nodesx(0) := 1
nodesy(0) := 0
currentpos := 1
! **********************************************************
! solution_found: called each time a solution is found
! **********************************************************
procedure solution_found
writeln("A solution has been found:")
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))
svgaddtext("SolGraph",
nodesx(currentpos-1), nodesy(currentpos-1),
"S(" + getsol(twt) + ")")
svgrefresh
end-procedure
! **********************************************************
! node_explored: called each time a node is explored
! **********************************************************
procedure node_explored
nodesx(currentpos) += 1
if (nodesx(currentpos-1)>nodesx(currentpos)) then
nodesx(currentpos) := nodesx(currentpos-1)
end-if
nodesy(currentpos) := -currentpos
writeln("[Node explored depth: " , (-nodesy(currentpos)) , "]")
svgrefresh
end-procedure
! **********************************************************
! go_down_branch: called each time the search goes down
! a branch of the search tree
! **********************************************************
procedure go_down_branch
writeln("[Branch go_down " , (-nodesy(currentpos)) , "]")
svgaddarrow("DownGraph",
nodesx(currentpos-1), nodesy(currentpos-1),
nodesx(currentpos), nodesy(currentpos))
currentpos := currentpos + 1
svgrefresh
end-procedure
! **********************************************************
! go_up_branch: called each time the search goes up
! a branch of the search tree
! **********************************************************
procedure go_up_branch
currentpos := currentpos - 1
writeln("[Branch go_up " , (-nodesy(currentpos)) , "]")
svgaddarrow("UpGraph",
nodesx(currentpos), nodesy(currentpos),
nodesx(currentpos-1), nodesy(currentpos-1))
svgrefresh
end-procedure
! **********************************************************
! Problem definition
! **********************************************************
DUR :: [21,53,95,55,34]
DUE :: [66,101,232,125,30]
WEIGHT :: [1,2,3,4,5]
setname(twt, "Total weighted tardiness")
zeroVar = 0
setname(zeroVar, "zeroVar")
! Setting up the decision variables
forall (t in TASKS) do
start(t) >= 0
setname(start(t), "Start("+t+")")
DURs(start(t)):= DUR(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
disjunctive(union(t in TASKS) {start(t)}, DURs, Disj, 1)
! The setxxxcallback methods must be called before
! setting the branching with 'cp_set_branching'
cp_set_solution_callback("solution_found")
cp_set_node_callback("node_explored")
cp_set_branch_callback("go_down_branch", "go_up_branch")
Strategy(0):= settle_disjunction
Strategy(1):= split_domain(KALIS_MAX_DEGREE,KALIS_MIDDLE_VALUE)
cp_set_branching(Strategy)
if not(cp_minimize(twt)) then
writeln("Problem is inconsistent")
exit(0)
end-if
svgwaitclose("Close browser window to terminate model execution.", 1)
end-model
|
