Initializing help system before first use

Branching strategies
Type: Programming
Rating: 3 (intermediate)
Description: Branching schemes for the enumeration of decision variables (discrete or continuous), disjunctive constraints, or tasks can be configured to use built-in or user-defined variable / constraint / task and value selection heuristics.
  • branching.mos: branching strategies using the branching schemes 'assign_and_forbid', 'assign_var', and 'split_domain'; user-defined variable and value selection heuristics.
  • probeac2001.mos, probeac2001_nary.mos: branching scheme 'probe_assign_var' and definition of generic binary or nary constraints; solving the Euler knight tour problem.
  • [probe]settledisjunction.mos: branching schemes 'probe_settle_disjunction' and 'settle_disjunction'; same problem as in "disjunctive.mos" but modeled by pairs of individual disjunctions (using 'or').
  • taskserializer.mos: defining a task-based branching strategy for the problem of "producer_consumer.mos"
File(s): branching.mos, probeac2001.mos, probeac2001_nary.mos, probesettledisjunction.mos, settledisjunction.mos, taskserializer.mos

branching.mos
(!****************************************************************
   CP example problems
   ===================
   
   file branching.mos
   ``````````````````
   User branching variable and value choice.
   The model parameter `ALG' selects one of the predefined
   branching strategies.

   (c) 2008 Artelys S.A. and Fair Isaac Corporation
       Creation: 2005, rev. 2007, rev. Sep. 2018
*****************************************************************!)
model "User branching"
 uses "kalis"

 parameters
  ALG=1
 end-parameters

 forward public function varchoice(Vars: cpvarlist): integer
 forward public function varchoice2(Vars: cpvarlist): integer
 forward public function valchoice(x: cpvar): integer
 forward public function valchoice2(x: cpvar): integer
  
 setparam("KALIS_DEFAULT_LB", 0); 
 setparam("KALIS_DEFAULT_UB", 20)
 
 declarations
  R = 1..10
  y: array(R) of cpvar
  C: array(R) of integer
  Strategy: array(range) of cpbranching
 end-declarations
 
 C:: [4, 7, 2, 6, 9, 0,-1, 3, 8,-2]
 
 all_different(y)
 forall(i in R | isodd(i)) y(i) >= y(i+1) + 1
 y(4) + y(1) = 13; y(8) <= 15; y(7) <> 5

! Definition of user branching strategies:
 Strategy(1):= assign_and_forbid("varchoice2", "valchoice", y)
 Strategy(2):= assign_var("varchoice", "valchoice", y)
 Strategy(3):= split_domain("varchoice", "valchoice2", y, true, 2)
 Strategy(4):= split_domain("varchoice2", "valchoice", y, false, 5)

! Select a branching strategy
 cp_set_branching(Strategy(ALG))
 
 if cp_find_next_sol then
  forall(i in R) write(getsol(y(i)), " ")
  writeln
 end-if
 
!---------------------------------------------------------------
! **** Variable choice ****
! **** Choose variable with largest degree + smallest domain
 public function varchoice(Vars: cpvarlist): integer
  declarations
   Vset,Iset: set of integer
  end-declarations

 ! Get the number of elements of "Vars"
  listsize:= getsize(Vars)  

 ! Set on uninstantiated variables
  forall(i in 1..listsize) 
   if not is_fixed(getvar(Vars,i)) then Vset+= {i}; end-if
 
  if Vset={} then
   returned:= 0
  else 
  ! Get the variables with max. degree
   dmax:= max(i in Vset) getdegree(getvar(Vars,i)) 
   forall(i in Vset)
    if getdegree(getvar(Vars,i)) = dmax then Iset+= {i}; end-if
   dsize:= MAX_INT

  ! Choose var. with smallest domain among those indexed by 'Iset'
   forall(i in Iset)
    if getsize(getvar(Vars,i)) < dsize then
     returned:= i
     dsize:= getsize(getvar(Vars,i)) 
    end-if 
  end-if 
  writeln(returned)
 end-function


! **** Choose variable y(i) with smallest value of C(i)
 public function varchoice2(Vars: cpvarlist): integer
  declarations
   Vset,Iset: set of integer
   VarInd: array(Iset) of integer
  end-declarations
 
 ! Set on uninstantiated variables
  listsize:= getsize(Vars)  
  forall(i in 1..listsize) 
   if not is_fixed(getvar(Vars,i)) then Vset+= {i}; end-if
 
  if getsize(Vset)=0 then
   returned:= 0
  else    
  ! Establish a correspondence of indices between 'Vars' and 'y' 
   forall(i in R)
    forall(j in Vset)
    if is_same(getvar(Vars,j), y(i)) then
     VarInd(i):= j
     Vset -= {j}
     break 1
    end-if

  ! Choose the variable
   imin:= min(i in Iset) i; cmin:= C(imin)
   forall(i in Iset)
    if C(i) < cmin then
     imin:= i; cmin:= C(i)
    end-if  
   returned:= VarInd(imin) 
  end-if
  writeln(imin, " ", returned)
 end-function
 
!---------------------------------------------------------------
! *** Value choice ****
! **** Choose the next value one third larger than lower bound 
! (Strategy may be used with any branching scheme since it 
!  makes sure that the chosen value lies in the domain)
 public function valchoice(x: cpvar): integer
!  returned:= getlb(x)
  returned:= getnext(x, getlb(x) + round((getub(x)-getlb(x))/3))
  writeln("Value: ", returned, " ", contains(x,returned), 
          " x: ",  x)
 end-function

! **** Split the domain into lower third and upper two thirds
! (Strategy to be used only with 'split_domain' branching since 
!  the chosen value may not be in the domain)
 public function valchoice2(x: cpvar): integer
  returned:= getlb(x) + round((getub(x)-getlb(x))/3)
  writeln("Value: ", returned, " x: ", x)
 end-function 
end-model
probeac2001.mos
(!****************************************************************
   CP example problems
   ===================
   
   file probeac2001.mos
   ````````````````````
   Euler knight tour problem implemented with user-defined
   binary constraints.
   
   (c) 2008 Artelys S.A. and Fair Isaac Corporation
       Creation: 2005, rev. Sep. 2018   
*****************************************************************!) 
model "Euler Knight Moves"
 uses "kalis"

 parameters
  S = 8                                  ! No. of rows/columns
 end-parameters
 
 N:= S * S                               ! Total number of cells
 setparam("KALIS_DEFAULT_LB", 0)
 setparam("KALIS_DEFAULT_UB", N-1)

 forward public function valid_knight_move(a:integer, b:integer): boolean

 declarations
  PATH = 1..N                            ! Cells on the board
  pos: array(PATH) of cpvar              ! Position p in tour
 end-declarations

! Setting names of decision variables
 forall(i in PATH) setname(pos(i), "Position"+i)  

! Fix the start position
 pos(1) = 0

! Each cell is visited once
 all_different(pos, KALIS_GEN_ARC_CONSISTENCY)

! The knight's path obeys the chess rules for valid knight moves
 forall(i in 1..N-1)
  generic_binary_constraint(pos(i), pos(i+1), "valid_knight_move")
 generic_binary_constraint(pos(N), pos(1), "valid_knight_move")

! Setting enumeration parameters
 cp_set_branching(probe_assign_var(KALIS_SMALLEST_MIN, 
                  KALIS_MAX_TO_MIN, pos, 14))

! Search for up to NBSOL solutions
 solct:= 0
 if not cp_find_next_sol then
  writeln("No solution")
 else
  writeln(pos)
 end-if

! **** Test whether the move from a to b is admissible ****
 public function valid_knight_move(a:integer, b:integer): boolean
  declarations
   xa,ya,xb,yb,delta_x,delta_y: integer
  end-declarations
  xa := a div S
  ya := a mod S
  xb := b div S
  yb := b mod S
  delta_x := abs(xa-xb)
  delta_y := abs(ya-yb)
  returned := (delta_x<=2) and (delta_y<=2) and (delta_x+delta_y=3)
 end-function

end-model
probeac2001_nary.mos
(!****************************************************************
   CP example problems
   ===================

   file probeac2001_nary.mos
   `````````````````````````
   Euler knight tour problem implemented with user-defined
   binary constraints.
   -- n-ary formulation version --

   (c) 2008 Artelys S.A. and Fair Isaac Corporation
       Creation: May 2005, rev. Apr. 2019
*****************************************************************!)
model "Euler Knight Moves"
 uses "kalis"

 parameters
  S = 8                                  ! No. of rows/columns
 end-parameters

 N:= S * S                               ! Total number of cells
 setparam("KALIS_DEFAULT_LB", 0)
 setparam("KALIS_DEFAULT_UB", N-1)

 forward public function valid_knight_move(vals: cptuple, s: integer): boolean

 declarations
  PATH = 1..N                            ! Cells on the board
  pos: array(PATH) of cpvar              ! Position p in tour
  propagation : integer                  ! Alg choice: 0, 1, or 2
 end-declarations

! Selecting the propagation algorithm for the generic nary constraint
 propagation := 0

! Setting names of decision variables
 forall(i in PATH) setname(pos(i), "Position"+i)

! Fix the start position
 pos(1) = 0

! Each cell is visited once
 all_different(pos, KALIS_GEN_ARC_CONSISTENCY)

! The knight's path obeys the chess rules for valid knight moves
 forall(i in 1..N-1)
  generic_nary_constraint({pos(i), pos(i+1)}, "valid_knight_move",propagation,S)
 generic_nary_constraint({pos(N), pos(1)}, "valid_knight_move",propagation,S)

! Setting enumeration parameters
 cp_set_branching(probe_assign_var(KALIS_SMALLEST_MIN,
                  KALIS_MAX_TO_MIN, pos, 14))

! Search for up to NBSOL solutions
 solct:= 0
 if not cp_find_next_sol then
  writeln("No solution")
 else
  writeln(pos)
 end-if

! **** Test whether the move from a to b is admissible ****
 public function valid_knight_move(vals: cptuple, s: integer): boolean
  declarations
   xa,ya,xb,yb,delta_x,delta_y: integer
   a,b : integer
  end-declarations
  ! Current position data
  a := getelt(vals,1)  ! 1 : pos(i)
  b := getelt(vals,2)  ! 2 : pos(i+1)

  xa := a div s
  ya := a mod s
  xb := b div s
  yb := b mod s
  delta_x := abs(xa-xb)
  delta_y := abs(ya-yb)
  returned := (delta_x<=2) and (delta_y<=2) and (delta_x+delta_y=3)
 end-function

end-model
probesettledisjunction.mos
(!****************************************************************
   CP example problems
   ===================
   
   file probesettledisjunction.mos
   ```````````````````````````````
   Scheduling disjunctive tasks with a probe-settle-disjunctions strategy.

   (c) 2008 Artelys S.A. and Fair Isaac Corporation       

*****************************************************************!)
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
settledisjunction.mos
(!****************************************************************
   CP example problems
   ===================
   
   file settledisjunction.mos
   ``````````````````````````
   Scheduling disjunctive tasks.

   (c) 2008 Artelys S.A. and Fair Isaac Corporation
       Creation: 2005, rev. 2007
*****************************************************************!)
model "Disjunctive scheduling with 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
  setname(start(t), "Start("+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 
 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):= settle_disjunction
 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("[", getsol(start(t)), "==>",
          getsol(start(t)) + DUR(t), "]:\t ",
	  getsol(tardiness(t)), "  (", getsol(tmp(t)), ")")     
 writeln("Total weighted tardiness: ", getsol(twt))
  
end-model
taskserializer.mos
(!****************************************************************
   CP example problems
   ===================
   
   file taskserializer.mos
   ```````````````````````
   Resource-constrained project planning problem (construction of 
   a house) modeled with task and resource objects.
   - Defining a task-based branching strategy -

   (c) 2008 Artelys S.A. and Fair Isaac Corporation
       rev. Sep. 2018
*****************************************************************!)
model "Tasks 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  
 end-declarations

 forward public function selectNextTask(tasks: cptasklist) : integer 

! '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 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 task_serialize: 
! - the task serialization process will use the function  
!   "selectNextTask" to look for the next task to fix
! - it will use the "KALIS_MAX_TO_MIN" value selection heuristic  
!   to set the tasks duration variable 
! - and the "KALIS_MIN_TO_MAX" value selection heuristic to set  
!   the start of the task
 cp_set_branching(task_serialize("selectNextTask", 
                  KALIS_MAX_TO_MIN, KALIS_MIN_TO_MAX, taskset))
 
! 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 task to schedule
 public function selectNextTask(tasks: cptasklist) : integer 
  write("selectNextTask : ")
  declarations
   Vset,Iset: set of integer
  end-declarations

 ! Get the number of elements of "tasks"
  listsize:= getsize(tasks)  

 ! Set of uninstantiated variables
  forall(i in 1..listsize) 
   if not is_fixed(getstart(gettask(tasks,i))) or 
      not is_fixed(getduration(gettask(tasks,i))) then 
     Vset+= {i};     
   end-if
 
  if Vset={} then
    returned:= 0
  else    
  ! Get the variables with max. degree
    dmax:= max(i in Vset) getsize(getduration(gettask(tasks,i))) 
    forall(i in Vset)
      if getsize(getduration(gettask(tasks,i))) = dmax then 
       Iset+= {i}; end-if
    dsize:= MAX_INT

  ! Choose var. with smallest domain among those indexed by 'Iset'
    forall(i in Iset)
      if getsize(getstart(gettask(tasks,i))) < dsize then
        returned:= i
        dsize:= getsize(getstart(gettask(tasks,i))) 
      end-if 
  end-if 

  if (returned <> 0) then
   writeln(gettask(tasks,returned))
  end-if
 end-function

end-model
Parent Topic Examples from the Xpress Kalis Reference Manual

© 2001-2019 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.