Examination Timetabling Resources

The general aim of this page is to collect together benchmark instances, solutions and software tools for examination timetabling. Specific aims are:

• To do so in the format(s) arising from the ITC2007 examination timetabling track, and so allow people to use one input/output forrmat across a wider variety of benchmark instances.
• Whenever possible to provide provably optimal solutions and so help with the evaluation of meta-heuristic solvers.

An integer programming encoding of the ITC 2007 format given in this preprint. A version coded in OPL/CPLEX is also available - please email me if you would like a copy; there are various versions and so would need to discuss which one meets your needs, there are also various programs to convert the data from ITC format to the data files that OPL/CPLEX can use. A potentially usable version is here TTC07exam.mod.

NEW: Aug 2011: TTC07tools.zip Contains an executable to convert .exam and .sln files to OPL format/format and so support verification of solutions or allow experimentation with better integer programming encodings.

Useful Links

• Page of Rong Qu (Nottingham) on examination timetabling
• ftp://ftp.mie.utoronto.ca/pub/carter/testprob
• ITC 2007 and specifically the examination timetabling track
• Tomas Müller code and paper (winning submission to 2 track of ITC 2007)

Yeditepe Instances for PATAT 2010 paper

INSTANCES FOR PATAT 2010 ARE HERE. Please note that the room sizes can been selected fairly arbitrarily and should be edited to the required values.

An example of a solution is yue20023.PF.132.70.sln which is optimal (and on the Pareto Front) for a room size of 132, and has cost 70. A fuller list of solutions will appear here in future; or email to get them sooner.

Small Sample Instance used in PATAT 2008

Given a straightfoward MILP encoding, then OPL/CPLEX could not cope with the size of the real instances. Hence, created a small instance by arbitrarily cutting out exams etc from a real instance until it was small enough for the OPL/CPLEX to solve.

The instance (33 exams): exam_comp_set4.test3.exam

An optimal solution (cost=88): exam_comp_set4.test3.sln
(Took about a week of CPLEX10 runtime to prove this optimal with the direct OPL encoding - but there probably are many ways it could be vastly improved - e.g. do clique cuts or other branch-and-cut, etc.)

Pareto Results

The resulting tradeoff curve: exam_comp_set4.test3.PF.ps

Some more associated .sln files:
exam_comp_set4.test3.sln
exam_comp_set4.test3.sln.BSF
exam_comp_set4.test3.sln.BSF.120
exam_comp_set4.test3.sln.BSF.89
exam_comp_set4.test3.sln.BSF.99
"MO.x.y" refers to runs with weights x and y for the two aggregated objectives.
exam_comp_set4.test3.sln.MO.1.10000
exam_comp_set4.test3.sln.MO.10000.1
exam_comp_set4.test3.sln.MO.2.1