Hybrid CP+LNS for the
CurriculumBased Course Timetabling Problem
Tommaso Urli
Scheduling and TimeTabling Group
DIEGM — University of Udine, Italy
CP 2013 Doctoral Program // Uppsala (Sweden), September 16, 2013
Outline of the talk
Covered topics
 Problem definition
Involved entities, hard and soft constraints
 CP model
Variables, constraints and cost components
 Solution technique
Branch & bound, Large Neighborhood Search
 Parameter tuning
Choice of intervals, sampling technique, tuning algorithm
 Results and conclusions
Problem definition
Course Timetabling
In general, Course Timetabling (CTT) [Schaerf, 1999] deals with
 Generating university timetables
by scheduling weekly or monthly lectures
 Subject to constraints based on
conflicts between courses and availability of teachers
 Minimizing costs
related to resources and user discomfort
 Actually, a family of problems
various formulations, typically determined by the nature of the conflicts
CurriculumBased Course Timetabling
In CurriculumBased Course Timetabling (CBCTT) [Bonutti et al., 2012]
 Students enrol to curricula (collections of courses)
a student enrolled in a curriculum must attend all of its courses
 Conflicts arise from
 courses in the same curriculum, and
 courses taught by the same teacher

Courses may be shared
in general, curricula are not disjoint, and a course may exist in more than one curriculum
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 fixed 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 * (wk).
 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.
CP model
CP model
 Problem modeled in GECODE (v4.2.0)
 popular C++ framework for CP
 open source (MIT License, very permissive)
 very well designed, extensible, highly recommended
 Complete source code available

Feel free to improve the model, the engine
 and, maybe, let me know how far you get
Variables
 Decision variables
 one roomslot variable for every lecture l ∈ L
 roomslot_{l} ∈ {1...R·P}
 specifying in which room and period (day, timeslot) to schedule the lecture
 In addition
 a number of redundant variables, only for modeling convenience
 day_{l} ∈ {1 ... D}
 period_{l} ∈ {1 ... P}
 timeslot_{l} ∈ {1 ... T}
 room_{l} ∈ {1 ... R}
 and the corresponding channelings with roomslot
Constraints
 Lectures & Room Occupancy
Modeled by imposing an alldifferent constraint on the decision variables
distinct(*this, roomslot);
 Conflicts
We impose constraints (also redundant) on lectures of conflicting courses
for (unsigned int c = 0; c < in.Courses(); c++)
for (unsigned int l1 = 0; l1 < in.CourseVector(c).Lectures()  1; l1++)
for (unsigned int l2 = l1 + 1; l2 < in.CourseVector(c).Lectures(); l2++)
{
int cl1 = index_of_start_lecture[c]+l1, cl2 = index_of_start_lecture[c]+l2;
// We use < instead of != for symmetry breaking
rel(*this, period[cl1] < period[cl2]);
// We enforce the constraint on roomslot, even if this is implied (redundant)
rel(*this, roomslot[cl1] < roomslot[cl2]);
// Implies the same on days and timeslots (redundant)
rel(*this, (day[cl1] == day[cl2]) >> (timeslot[cl1] < timeslot[cl2]));
rel(*this, (timeslot[cl1] == timeslot[cl2]) >> (day[cl1] < day[cl2]));
}
Constraints
 Availability
Modeled by constraining period_{l} != p if teacher_{l} is not available at period p
for (unsigned int c = 0; c < in.Courses(); c++)
for (unsigned int p = 0; p < in.Periods(); p++)
{
// Skip constraint posting if course is available
if (in.Available(c, p))
continue;
// Post constraint on each lecture of the course
for (unsigned int l = 0; l < in.CourseVector(c).Lectures(); l++)
{
rel(*this, period[index_of_start_lecture[c] + l] != p);
// As before, this is implied, but nonetheless it helps propagation (redundant)
for (unsigned int r = 0; r < in.Rooms(); r++)
rel(*this, roomslot[index_of_start_lecture[c] + l] != p * in.Rooms() + r);
}
}

Lectures and Conflicts constraints can be relaxed by using
nvalues
and
count
constraints on free variables, and then adding them to the cost.
Cost
For each soft constraint we added an extra variable to count the violations. The counting is carried out by various constraints
 Room stability
nvalues
constraint on the room used by each course
 Minimum working days
cardinality
constraint (+ set vars.) on the days covered by each course
 Isolated lectures
cardinality
constraint on adjacent timeslot variables for each course
Cost
Solution technique
Large Neighborhood Search [Shaw, 1998]
Main ideas
 Growing neighborhood and restarts
 we start by releasing d = d_{min} = 2 variables
 if d · iter_{max} iterations go without improvement d is increased
 if d grows as far as d_{max} · L, a restart is performed
 Adaptive d_{min}
at each restart, the d_{min} is set to the value that, during the run, has yielded
the highest number of improving solutions
Main ideas
Main ideas
Cutoffs [Johnson et al., 1989]
In classic SA, the temperature t decreases when n neighbors have been
visited
In SA with cutoffs, the temperature decreases when k
neighbors have been accepted (which occurs much often at the beginning, so adaptively wrt. search history)
Parameter tuning
Parameter tuning
 Identify reasonable parameter intervals
 d_{min} ∈ {1,2,3}
 d_{max} ∈ {0.05, 0.1, 0.15}
 iter_{max} ∈ [150, 350]
 t_{var} ∈ {5, 7.5, 10} (milliseconds, timeout for B&B to fix a variable)
 λ ∈ {0.95, 0.97, 0.99} (cooling rate for SA)
 ρ ∈ [1, 50] (neighbors accepted for each temperature step)
 t_{min} ∈ [0.1, 1.0] (minimum temperature for SA)
 t_{init} ∈ [1.0, 100] (initial temperature for SA)
 r_{rand} ∈ [0.05, 0.2]
 Sample 96 configurations from the Hammersley point set
Tuning outcome
Find best configuration by running FRace [Birattari et al., 2010] over a heterogeneous
set of instances using json2run. Best configuration
 d_{min} = 2
 d_{max} = 0.05
 iter_{max} ~250
 t_{var} ∈ = 10
 λ = 0.97
 ρ = 5
 t_{min} ∈ 0.25
 t_{init} = 35
 r_{rand} = 0.15
Results & Conclusions
Validation on ITC 2007 instances
Validation on the 21 instances from the ITC 2007 competition.
Conclusions
 Far from outperforming the best heuristics in literature
 between 2x to 3x higher costs (but not orders of magnitude higher)
 Yet, practical approach
 CP provides a powerful modeling language (global constraints, set variables, ...)
 LNS integrates seamlessly with CP
 relatively easy to add constraints, cost components, custom destroy heuristics
 worst case, a random approach can still tackle large instances
 Performance can be improved
 increase propagation through channeled models
 better destroy heuristics
Thank you