Note: This web-site may be updated from time to time. Please
check back often for changes.
Organized by Metaheuristics
Network and sponsored by PATAT the International
Timetabling Competition is open to any aspiring timetabler! The problem proposed
is to create a weekly timetable for a university. Below you can find details
on the problem and all information necessary to take part to the competition.
31st March 2003 Midnight Greenwich Mean Time
How to take part
have to implement an algorithm to tackle the problem on a single processor
machine, they can use any programming language.
goal is to produce feasible class timetables, in which a number of hard
constraints are satisfied, and to minimize the number of broken soft constraints.
All instances proposed will have at least a perfect solution, that is a
solution with no constraint violations, hard or soft.
instances of different size and type will appear on the web site from October
1st 2002. Two weeks before the deadline ten more instances will be placed
on the web from March 17th 2003.
have to benchmark their machine with a program provided below in order to
know for how much time they can run their program on their machines.
- The algorithms should run on
a single processor machine, take as input a problem file in the format described,
and produce as output a feasible timetable (if found) with a minimum number
of soft constraint violations in the allowed CPU time. Obviously the algorithm
should not take account of additional knowledge about the instance (e.g.
results from previous runs). The same version (and fixed parameters) of
the algorithm must be used for all instances. That is, the algorithm should
not "know" which instance it is solving - while your particular
algorithm might analyse the problem instance and set parameters accordingly,
it should not "recognise" the particular instance.
should submit for each instance the best solution found by their algorithm
in the specified computer time, by uploading it onto the web site.
- Participants should also submit
a concise and clear description of their algorithm, so that others can implement
deadline for uploading the solutions to all twenty instances, and the algorithm
description, onto the website is March 31st 2003 (midnight GMT).
winner must be prepared to show that those results are repeatable in the
given computer time. In particular the participants should make their program
in such a way that the EXACT run that produced each solution submitted can
be repeated (by providing the random seed etc.). You can try several runs
to produce each submitted solution (each with the allowed computer time),
but you must be able to repeat the run for any solution submitted. Possible
winners will be expected to demonstrate their program on existing and new
unseen instances. In some circumstances, possible winners may be
required to show source code to a limited number of Network Members. This
is simply to check that you have stuck to the rules.
who cannot provide feasible solutions to all twenty instances are excluded
from the competition.
winner is the participant that reaches the best results across all instances.
See here for details on the exact way
results will be compared.
€300 and 1 free registration
to the PATAT 2004 conference.
Network is a European Commission project, undertaken jointly by five European
institutes, that aims to compare and analyse the performance of various metaheuristics
on different combinatorial optimization problems, including Timetabling.
The International Series of Conferences
on the Practice and Theory of Automated Timetabling (PATAT) is held
bi-annually as a forum for both researchers and practioners of timetabling
to exchange ideas.
by IDSIA, Manno, Switzerland.