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
BranchingSchemes/SettleDisjunction.png

Synopsis

function probe_settle_disjunction(disjunctions:set of cpctr, probeLevel:integer) : cpbranching

function probe_settle_disjunction(disj_selector:function or string, disjunctions:set of cpctr, probeLevel:integer) : cpbranching

function probe_settle_disjunction(disj_selector:function or 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:function or string, probeLevel:integer) : cpbranching

function probe_settle_disjunction(probeLevel:integer) : cpbranching

Arguments

disj_selector	the disjunction selector name (pre-defined constant, name of user-defined function or reference to user-defined function)
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", "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

Contents

Index

Glossary

Search Results

probe_settle_disjunction