A Simulated Annealing approach to the
CurriculumBased Course Timetabling problem
Ruggero Bellio^{1},
Sara Ceschia^{2},
Luca Di Gaspero^{2},
Andrea Schaerf^{2},
and Tommaso Urli^{2}
DIES^{1}, DIEGM^{2} — University of Udine, Italy
MISTA 2013 // Ghent (Belgium), August 27, 2013
Outline of the talk
Covered topics
 Problem definition
Involved entities, hard and soft constraints (cost components)
 Solution technique
Metaheuristic, neighborhood relations
 Tuning process
Choice of intervals, sampling technique, tuning algorithm
 Results
 Future (and current) work
Adaptive tuning, preliminary results
Problem definition
Problem
Course Timetabling (CTT) deals with
generating university timetables by scheduling weekly lectures,
subject to conflicts and availability constraints, while minimizing
costs related to resources and user discomfort
In CurriculumBased Course Timetabling (CBCTT),
conflicts originate from curricula,
i.e, collections of related courses whose lectures cannot be scheduled at
the same time.
Entities
CBCTT involves several entities
 Courses & Lectures.
 A course is composed by several
lectures to be scheduled at different times. Each course is taught by a
teacher, who might be unavailable
at certain times, and its lectures must be scattered over a
minimum number of working days.
 Curricula.
 Each student enrols in a curriculum, i.e., a collection
of courses whose lectures must be all attended by the enrolled students.
Entities
 Days × Timeslots = Periods.
 Lectures can be scheduled over a set of days,
each one subdivided in a number of timeslots. A
(day, timeslot) pair identifies a period,
unique within a week, in which a lecture can be scheduled.
 Rooms & Roomslots.
 In addition to a period, a valid schedule must specify a room
for each lecture. A room has a fixed capacity, i.e. a maximum
number of seats. Additionally, a (room, period) is typically
called a roomslot.
Hard constraints
A feasible solution must satisfy the following hard constraints
 Lectures.
 Each lecture must be scheduled (in one and only one roomslot).
 Conflicts.
 Lectures pertaining to courses in the same curriculum or taught by the same teacher
must be assigned different periods.
 Room Occupancy.
 Two lectures cannot take place in the
same roomslot.
 Availability.
 Each lecture must be scheduled when the teacher teaching it is available.
Soft constraints (cost components)
 Room Capacity.
 When a lecture with n students gets scheduled in a room of capacity
k < n, the cost of the solution increases by nk.
 Room Stability.
 All the lectures of a course should be scheduled in the same room, every extra room
increases the cost of the solution by one.
 Minimum Working Days.
 Every time a course with w minimum working days is scheduled over k < w
days, the cost of the solution increases by 5 * (wn).
 Isolated Lectures.
 Every time a scheduled lecture is not preceded or followed by lectures of courses in the same
curriculum, the cost of the solution increases by 2.
Solution technique
Basic ideas
 Simulated annealing

Nongeometric cooling scheme (cutoffs),
allows to "save" iterations in the beginning of the search, to promote
intensification in the end

Stopping condition based on iterations (minimum temperature is just a target)

Two neighborhoods: MoveLecture and SwapLectures
 Extensive tuning

Using a finegrained FRace starting from the Hammersley point set

Over 4200 generated instances from [SmithMiles and Lopes, 2010]

Validation over the 21 ITC 2007 competition instances
Cutoffs [Johnson et al., 1989]
SA (temperature decreases when n neighbors have been
visited, constant decrease)
SA with cutoffs (temperature decreases when k
neighbors have been accepted, i.e., much more often in
the beginning because of high temperature, adaptive)
Neighborhood relations
Given a solution, we explore two possible, neighborhoods
 MoveLecture

 Move one lecture from its currently assigned period and room to
another period and/or a free room.
 SwapLectures
 Take two lectures of distinct courses in different periods and swap their
periods and their rooms.

At each step we choose stochastically the neighborhood to explore,
where the probability of selecting the second one is a parameter of the algorithm.
Algorithm overview
(actually implemented in EasyLocal++)
best = current = randomSolution();
sampled = accepted = 0;
while (iterations <= maxIterations)
{
current = random() < swapRate ? SwapLecture(best) : MoveLecture(best);
sampled++;
delta = cost(current)  cost(best);
if (delta <= 0 or (random() < e^(delta/T))) {
best = current;
accepted++;
}
if (sampled >= maxSampled or accepted >= maxAccepted) {
T *= alpha;
sampled = accepted = 0;
}
}
Tuning process
Parameters
We have tuned all of our parameters at once by
 Fixing some parameters based on experience
 Selecting appropriate intervals for the other
 Start temperature st ∈ [1, 100]
 Minimum temperature mt ∈ [0, 1]
 Swap rate sr ∈ [0, 1]
 Ratio of neighbors accepted (over sampled)
ρ ∈ [0, 1]
Stopping condition variables
 First, we compute how many temperature steps are needed to get from st
to mt in the given number of iterations by using a cooling rate of cr
nt =  log ( st / mt ) / log( cr )
 Then we compute how many neighbors can be sampled for each temperature
maxSampled = maxIterations / nt
 Finally, we compute how many neighbors can be accepted for each temperature
maxAccepted = ρ * maxSampled
Hammersley point set
We sampled 32 parameter configurations from the Hammersley point set, which has some nice
properties that make it good for parameter tuning.
 Lowdiscrepancy
Randomlooking but spacefilling points
 Arbitrary number of parameters
Although lowdiscrepancy is less good in higher dimensions
 Arbitrary number of samples
i.e., tuning can be finegrained at will
FRace
We run an FRace among our 32 configurations on the 4200 instances from [SmithMiles and Lopes, 2010]. The winning setup was
 Start temperature st = 5.424
 Minimum temperature mt = 1e06
 Swap rate sr = 0.45
 Ratio of neighbors accepted (over sampled) ρ = 0.022
The whole tuning process was automated with json2run (open source tool).
Results
Validation on ITC 2007 instances
Validation on the 21 instances from the ITC 2007 competition.
Future (and current) work
Adaptive tuning
 Idea: find rules to set parameters, rather than fixed values
 Our method (for a single parameter)
 Fix all parameters but the target one
 Run lots of experiments with many instances, many values for the target parameter, and many repetitions of the same experiment
 For each instance find the best value of the parameter
 Find a statistical model to predict the ideal value from the instance features
Adaptive tuning of start temperature
Adaptive tuning validation
Validation on the 21 instances from the ITC 2007 competition.
Adaptive tuning future
 Problem: double dependency
 Predictor based on experiments where
 Minimum temperature mt = 1e06
 Swap rate sr = 0.45
 Start temperature ρ = 0.022
 but these parameters were optimal when
 Start temperature st = 5.424
 therefore all parameters must be predicted together
 nontrivial, models become unreliable
 this is an ongoing work
Thank you