University Course Timetabling

using Integer Programming

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

The project aims at designing a search for university course timetabling, which essentially is the decision version of graph colouring with complex performance indicators ("soft constraints") for feasible solutions. We have tested several integer programming formulations of graph colouring and Udine Course Timetabling, which is now Track 3 of the second International Timetabling Competition (www). One of them, using a new IP formulation of set colouring, solves instance Udine1 to optimum within 91 seconds on a single processor, thanks to implicit symmetry breaking. A branch and cut procedure based on this formulation has produced some strong lower bounds for larger instances. Several heuristics based on searching large neighbourhoods using integer programming have also been designed and implemented. Some of them provide good solutions to data sets of 500+ events within an hour. An instance generator producing instances more realisic than pure G_n,p is also available. Further work may include integration of methods of constraint and semidefinite programming in the search.

Papers and Talks:

Semidefinite Programming Relaxations in Timetabling
introducing semidefinite programming relaxations of bounded graph colouring and certain other subproblems in timetabling
has been accepted to Practice and Theory of Timetabling (abstract). Presented at:

• Semidefinite Programming Relaxations in Timetabling,
  The 8th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2010, Queen's University Belfast, Ireland, August 10—13, 2010
• Semidefinite Programming Relaxations in Timetabling,
  The Automated Scheduling, Optimisation and Planning Seminar, ASAP, Nottingham, UK, May 25, 2010

A Branch-and-cut Procedure for the Udine Course Timetabling Problem
introducing five classes of cuts and an exact solver based on those,
has been accepted to Practice and Theory of Timetabling (pre-print, slides, BibTeX). Presented at:

• A Branch-and-cut Procedure for the Udine Course Timetabling Problem,
  The 7th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2008, Université de Montréal, August 19—22, 2008

Decomposition, Reformulation, and Diving in University Course Timetabling,
describing a hybrid solver generating and searching large neighbourhoods using integer programming,
Comput. Oper. Res. 37 (2010): 582--597 (DOI, pre-print, BibTeX). Presented at:

• Decomposition, Reformulation, and Diving,
  The Automated Scheduling, Optimisation and Planning Seminar, ASAP, Nottingham, UK, November 6, 2008 (slides)

On a Clique-Based Integer Programming Formulation of Vertex Colouring with Applications in Course Timetabling,
describing a transformation of graph colouring to graph multicolouring and its effects in applications,
has been submitted to a journal (pre-print also in arXiv, instances, some of which were obtained using the generator, BibTeX). Presented at:

• A Clique-Based Integer Programming Formulation of Graph Colouring and Applications,
  Seminar of the Centre for Discrete Mathematics and its Applications, DIMAP, Warwick University, UK, June 10, 2008 (slides)
• Integer Programming Formulations of Vertex Colouring,
  The Automated Scheduling, Optimisation and Planning Seminar, ASAP, Nottingham, UK, October 5, 2007 (slides)
• Variability of Integer Programming Models of Course Timetabling,
  European Conference on Operational Research, EURO XXII, Prague, CZ, July 8—11, 2007

Penalising Patterns in Timetables: Novel Integer Programming Formulations,
comparing five formulations of the most difficult soft constraint in Udine Course Timetabling,
appears in post-proceedings from OR2007 (paper, instances, some of which were obtained using the generator, results, an example plot for Udine1 and Udine2006-1, BibTeX). Presented at:

• Strengthened Integer Programming Formulation of Constraints Counting Matches of Patterns in Timetables,
  Operations Research 2007, OR 2007, Saarbruecken, Germany, September 4—7, 2007 (slides)
• Integer Programming Models of Course Timetabling,
  The Automated Scheduling, Optimisation and Planning Seminar, ASAP, Nottingham, UK, February 15, 2007

Uses and Abuses of MIP in Course Timetabling,
a poster presented at the 4th Mixed Integer Programming Workshop, MIP 2007, Montreal, CA, July 30 — August 2, 2007 (poster)

Software

The papers and talks above are based on the following open-source software:

• Memos Solver for Timetabling: Multiphase Exploitation of Multiple Objective-/Value-restricted Submodels for Udine Course Timetabling
• Branch-and-Cut Solver for Timetabling: A Branch-and-Cut Procedure for Udine Course Timetabling
• Random Instance Generator: Random Instance Generator for Udine Course Timetabling

Should you have any questions or comments, do not hesitate to contact Jakub <jakub at marecek dot cz>.

Go back to Jakub's homepage.