# Overview

Atlassian Sourcetree is a free Git and Mercurial client for Windows.

Atlassian Sourcetree is a free Git and Mercurial client for Mac.

# 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.

## Usage

Once compiled, the solver can be activated by running:

$ ./CPCourseTimetabling -time <timeout_in_msec> <ctt_instance_file>

Where the `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_variable`

how much time is dedicated to each variable when the sub-solver is called at each LNS*repair*iteration`-lns_constraint_type`

the 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_intensity`

maximum number of non-improving iterations before increasing the relaxation intensity`-lns_min_intensity`

minimum relaxation intensity (the semantics of this value is up to the developer of the model)`-lns_max_intensity`

maximum relaxation intensity (the semantics of this value is up to the developer of the model)`-lns_sa_start_temperature`

initial temperature for the Simulated Annealing acceptance criterion`-lns_sa_cooling_rate`

temperature decay factor for the Simulated Annealing acceptance criterion`-lns_sa_cooling_rate`

parameter 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.

## Building

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

$ make

to produce the solver executable.

## Licensing

The code is provided under the MIT License, except for the following files:

- faculty.hh
- faculty.cc

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.