group_serializer

Purpose

A branching scheme Group Serializer is a branching scheme of branching schemes. That means, it can be seen as a meta-branching scheme. The search can be decomposed into clusters of branching schemes that will be explored based upon a specific dynamic group selection heuristic. When a specific group is selected, the ordered branching scheme list of this group will be treated sequentially. Once all the branching schemes of the group have been treated, another branching scheme group is selected with the group selection heuristic. Note that the probing level of the overall group serializer is checked before the probing of the group branching scheme.
For example, the task_serializer branching scheme is a particular kind of group serializer heuristic tailored for task based search tree exploration. In this case a group corresponds to a task and the list of branching schemes is the following :

start time variable
duration variable

Synopsis

function group_serializer(groups: set of cpbsgroup, groupSelector: function or string) : cpbranching

function group_serializer(groups: set of cpbsgroup, groupSelector: function or string, probe: integer) : cpbranching

Arguments

groups	the set of branching scheme groups
groupselector	the group selection heuristic
probe	the probe level

Example

The following example shows how to implement a branching scheme group serializer with similar branching strategy to a task serializer:

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

Contents

Index

Glossary

Search Results

group_serializer