A Branch-and-Cut Procedure
for the Udine Course Timetabling Problem

a project of Jakub Marecek <jakub at marecek dot cz> (www)
supervised by Prof. Edmund K. Burke <ekb at cs dot nott dot ac dot uk> (www)
and Dr. Andrew J. Parkes <ajp at cs dot nott dot ac dot uk> (www)
and Dr. Hana Rudova <hanka at fi dot muni dot cz> (www).

An Overview

This is a branch-and-cut solver for the Udine Course Timetabling problem [Bonutti, De Cesco, Di Gaspero, and Schaerf, DOI]. In general terms, it is based on an alternative integer programming formulation. Instead of a + d b binary variables a c constraints, there are a binary variables and b integer variables bounded from above by d. Only c constraints are required initially and a number of ``Type 1'' constraints exponential in d is added only upon violation. A number of further ``Type 2'' cuts are also introduced. Although most Type 2 cuts are problem-specific, cuts exploiting integrality of the objective function seem to have wider applicability, as well as a lower bounding procedure based on an alternative enforcement of integrality.

In timetabling terms, the ``Type 1'' cuts stem from enumeration of event/ free-period patterns. ``Type 2'' cuts stem from patterns given by days of instruction and days off, the graph colouring component, and various implied bounds. An implementation of the corresponding branch-and-cut procedure is evaluated on the instances from Track 3 of the International Timetabling Competition 2007. Using IBM/ILOG CPLEX it is possible to find provably optimal solutions to two instances (comp01 and comp11) within 15 minutes and good lower bounds for several other instances within two hours.

The use of advanced features of ILOG Concert and ILOG CPLEX could be of interest to C++ programmers.

Downloads:

License:

The solver is licenced under the GNU Public License (GPL) version 3. It would be greatly appreciated if users cited the following paper in any work that uses it:

The pre-print of the paper is then presented only to ensure timely dissemination of scholarly and technical work. Copyright is retained by the respective copyright holders.


Go back to Jakub's homepage if you want.