University Course Timetabling

Random Instance Generator

developed by Jakub Marecek <jakub at marecek dot cz> (www).

Intro and Use

Timetabling is an NP-Hard extension of graph colouring, which has recently attracted considerable interest. As there often is a considerable structure to the graph, such as a Reversible Clique Partition considerably smaller than the graph itself, and a number of easy-to-identify don't-care and backdoor variables, such as the loosely-constrained Fridays and tightly-constrained lunch-time periods of the remaining four days, it is often possible to solve real-life instances of considerable size to optimality. Burke et al. have solved a number of instances with a couple of hundred courses each, for example. Many solvers for timetabling problems are, however, still benchmarked using instances obtained using the generator of Ben Paechter. Those don't have much of any structure, as they roughly correspond to the G_{n,p} random graphs. We have now produced a generator producing more realistic instances in the Udine Course Timetabling Problem format.

It is distributed as a pair of Python modules. To generate the CTT files, use: 

from udineGenUtils import TimetablingInstance

events = 200
occupancy = 70

instance = TimetablingInstance(events, occupancy)
print instance.genInstanceDef()

To generate Zimpl model definitions and (possibly also) the corresponding LP files, try: 

from udineGenUtils import *
from zimplUtils import outputZimpl

models = ["colouring", "scheduling"]

for occupancy in [70, 80, 90]:
  for events in [100, 200, 300]:
    for sample in range(3):
      instance = TimetablingInstance(events, occupancy)
      filename = "./instances/random_%i_%i_%i.ctt" % (events, occupancy, sample + 1) 
      output = open(filename, "w")
      output.write(instance.genInstanceDef())
      output.close()
      for model in models:
        outputZimpl(filename, model)

Notice that the instances are not "perfect" in that there often will be a considerable penalty in the optimal solution. The easiest way to ascertain the optimal value is to solve the integer programming instance obtained using Zimpl (in an LP file) with SCIP, CPLEX, or similar.

If you have any questions or comments, please don't hesitate to contact Jakub Marecek

Downloads and Conditions of Use

The code is distributed under LGPL in two Python modules, or you can download a number of pre-generated instances in a zip file.

If you find the generator useful, please cite one of our papers for which it was originally developed:

If you use the export to ZIMPL, please also cite ZIMPL as:


See more of Jakub's homepage or timetabling page, if you please.