Initializing help system before first use

# 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 :

1. start time variable
2. 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

Related topics
bs_group
Parent Topic Search

© 2001-2026 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.