probe_settle_disjunction
probe_settle_disjunction |
Purpose
Creates a probe_settle_disjunction branching scheme that resolves the status of all the disjunctions passed in argument. The branching consists in choosing one branch of the disjunction and posting the constraint stated by this branch. The branches are tested from left to right
Synopsis
function probe_settle_disjunction(disjunctions:set of cpctr, probeLevel:integer) : cpbranching
function probe_settle_disjunction(disj_selector:string, disjunctions:set of cpctr, probeLevel:integer) : cpbranching
function probe_settle_disjunction(disj_selector:string, disjunctions:array(range) of cpctr, probeLevel:integer) : cpbranching
function probe_settle_disjunction(disjunctions:array(range) of cpctr, probeLevel:integer) : cpbranching
function probe_settle_disjunction(disj_selector:string, probeLevel:integer) : cpbranching
function probe_settle_disjunction(probeLevel:integer) : cpbranching
Arguments
|
disj_selector
|
the disjunction selector name (pre-defined constant or user-defined function name)
|
|
disjunctions
|
the set or array of disjunctions
|
|
probeLevel
|
maximal probing level
|
Return value
The resulting probe_settle_disjunction branching scheme
Example
The following example shows how to use the probe_settle_disjunction branching scheme to solve a small disjunctive scheduling problem:The problem consists of finding a schedule for some tasks on one machine. The machine can process only one task at the time and the goal is to minimize the total weighted tardiness of the schedule. Note that the result may be (and will be in this case) suboptimal as the search tree is not fully explored.
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
Related topics