CP+LNS solver for (Curriculum-Based) Course Timetabling
Course Timetabling (CTT) is a popular combinatorial optimization problem which 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 Curriculum-Based Course Timetabling (CB-CTT), students enrol to curricula i.e., (possibly overlapping) collections of courses. Lectures of courses pertaining to the same curriculum must, therefore, be scheduled at different times, so that students can attend all courses.
This repository contains the following assets:
- a Constraint Programming (CP) model for the CB-CTT problem written in GECODE v4.2.0, and
- a Large Neighborhood Search (LNS) solver for the said model (implemented as a GECODE search meta-engine, i.e., an engine having one of the base engine as subcomponent).
Implementation note the first version of this solver was based on a less engineered engine, which was not in line with GECODE guidelines. In particular, the whole optimization run used to be carried out in a single call of
next(). The solver now relies on a more principled LNS meta-engine for GECODE by Luca Di Gaspero and me, that can be found at https://bitbucket.org/tunnuz/gecode-lns.
Once compiled, the solver can be activated by running:
$ ./CPCourseTimetabling -time <timeout_in_msec> <ctt_instance_file>
ctt_instance_file is an instance file in CTT or ECTT format (see http://satt.diegm.uniud.it/ctt for more details on the format and a lot of benchmark instances). Additional parameters can be passed to the LNS meta-engine, in particular:
-lns_time_per_variablehow much time is dedicated to each variable when the sub-solver is called at each LNS repair iteration
-lns_constraint_typethe kind of constraining which is done to the solution when the sub-solver is called at each LNS repair iteration (strict, loose, …)
-lns_max_iterations_per_intensitymaximum number of non-improving iterations before increasing the relaxation intensity
-lns_min_intensityminimum relaxation intensity (the semantics of this value is up to the developer of the model)
-lns_max_intensitymaximum relaxation intensity (the semantics of this value is up to the developer of the model)
-lns_sa_start_temperatureinitial temperature for the Simulated Annealing acceptance criterion
-lns_sa_cooling_ratetemperature decay factor for the Simulated Annealing acceptance criterion
-lns_sa_cooling_rateparameter to control cutoffs, i.e., number of accepted solutions at each temperature step in the Simulated Annealing acceptance criterion (see Johnson et al., 1989 for more information on cutoffs)
The parameters are set to reasonable defaults.
In order to compile the solver you'll need the following prerequisites:
- a C++11-compliant compiler and standard library, and
- GECODE v4.2.0
Also, update the
GECODE_LIBS variable in the Makefile, so that it points to the correct shared library path, e.g.,
/usr/local/lib. Then, run
to produce the solver executable.
The code is provided under the MIT License, except for the following files:
which are needed in order to read the instance files. Note that these files represent an obsolete, but functional, version of the instance reader. The most recent one (though not compatible with the solver's code) is openly available at http://www.diegm.uniud.it/schaerf/SAS/programmi/TimetablingEL.zip.