Optimization and enumeration

Optimization

Since running our model i4exam_ka.mos in Section Implementation has produced a solution to the problem that does not use all time slots one might wonder which is the minimum number of time slots that are required for this problem. This question leads us to the formulation of an optimization problem.

We introduce a new decision variable numslot over the same value range as the plan_i variables and add the constraints that this variable is greater or equal to every plan_i variable. A simplified formulation is to say that the variable numslot equals the maximum value of all plan_i variables.

The objective then is to minimize the value of numslot, which results in the following model.

model "I-4 Scheduling exams (CP) - 3"
 uses "kalis"

 declarations
  NT: integer                         ! Number of time slots
  EXAM: set of string                 ! Set of exams
  TIME: set of integer                ! Set of time slots
  INCOMP: dynamic array(EXAM,EXAM) of integer ! Incompatibility between exams

  plan: array(EXAM) of cpvar          ! Time slot for exam
  numslot: cpvar                      ! Number of time slots used
 end-declarations

 initializations from 'Data/i4exam2.dat'
  INCOMP NT
 end-initializations

 finalize(EXAM)
 TIME:= 1..NT

 setparam("kalis_default_lb", 1); setparam("kalis_default_ub", NT)
 forall(e in EXAM) create(plan(e))

! Respect incompatibilities
 forall(d,e in EXAM | exists(INCOMP(d,e)) and d<e)  plan(d) <> plan(e)

! Calculate number of time slots used
 numslot = maximum(plan)

! Solve the problem
 if not(cp_minimize(numslot)) then
  writeln("Problem is infeasible")
  exit(1)
 end-if

! Solution printing
 forall(t in TIME) do
  write("Slot ", t, ": ")
  forall(e in EXAM)
   if (getsol(plan(e))=t) then write(e," "); end-if
  writeln
 end-do

end-model

Instead of cp_find_next_sol we now use cp_minimize with the objective function variable numslot as function argument.

This program also generates a solution using seven time slots, thus proving that this is the least number of slots required to produce a feasible schedule.

Enumeration

When comparing the problem statistics obtained by adding a call to cp_show_stats to the end of the different versions of our model, we can see that switching from finding a feasible solution to optimization considerably increases the number of nodes explored by the CP solver.

So far we have simply relied on the default enumeration strategies of Xpress Kalis. We shall now try to see whether we can reduce the number of nodes explored and hence shorten the time spent by the search for proving optimality.

The default strategy of Kalis for enumerating finite domain variables corresponds to adding the statement

cp_set_branching(assign_var(KALIS_SMALLEST_DOMAIN, KALIS_MIN_TO_MAX)) 

before the start of the search. assign_var denotes the branching scheme (`a branch is formed by assigning the next chosen value to the branching variable'), KALIS_SMALLEST_DOMAIN is the variable selection strategy (`choose the variable with the smallest number of values remaining in its domain'), and KALIS_MIN_TO_MAX the value selection strategy (`from smallest to largest value').

Since we are minimizing the number of time slots, enumeration starting with the smallest value seems to be a good idea. We therefore keep the default value selection criterion. However, we may try to change the variable selection heuristic: replacing KALIS_SMALLEST_DOMAIN by KALIS_MAX_DEGREE results in a reduction of the tree size and search time to less than half of its default size.

Here follows once more the complete model.

model "I-4 Scheduling exams (CP) - 4"
 uses "kalis"

 declarations
  NT: integer                         ! Number of time slots
  EXAM: set of string                 ! Set of exams
  TIME: set of integer                ! Set of time slots
  INCOMP: dynamic array(EXAM,EXAM) of integer ! Incompatibility between exams

  plan: array(EXAM) of cpvar          ! Time slot for exam
  numslot: cpvar                      ! Number of time slots used
 end-declarations

 initializations from 'Data/i4exam2.dat'
  INCOMP NT
 end-initializations

 finalize(EXAM)
 TIME:= 1..NT

 setparam("kalis_default_lb", 1); setparam("kalis_default_ub", NT)
 forall(e in EXAM) create(plan(e))

! Respect incompatibilities
 forall(d,e in EXAM | exists(INCOMP(d,e)) and d<e)  plan(d) <> plan(e)

! Calculate number of time slots used
 numslot = maximum(plan)

! Setting parameters of the enumeration
 cp_set_branching(assign_var(KALIS_MAX_DEGREE, KALIS_MIN_TO_MAX))

! Solve the problem
 if not(cp_minimize(numslot)) then
  writeln("Problem is infeasible")
  exit(1)
 end-if

! Solution printing
 forall(t in TIME) do
  write("Slot ", t, ": ")
  forall(e in EXAM)
   if (getsol(plan(e))=t) then write(e," "); end-if
  writeln
 end-do

 cp_show_stats

end-model

NB: In the model versions without optimization we may try to obtain a more evenly distributed schedule by choosing values randomly, that is, by using the value selection criterion KALIS_RANDOM_VALUE instead of KALIS_MIN_TO_MAX.

Further detail on the definition of branching strategies is given in Chapter Enumeration.