Examination Timetabling Benchmark Datasets
 Purdue Final Examination Data Sets
The following nine examination data sets were collected using the UniTime application. The are all final examination problems from Purdue University, for each semester starting Fall 2008 when UniTime was used for examination timetabling at the university for the first time.

 Problem Characteristics
The data sets have the following properties:
Problem Fall 2012 Spring 2012 Fall 2011 Spring 2011
Exams1,8641,7981,9141,866
with exam seating819780827801
Students33,27931,59333,85631,688
Enrollments117,265111,345122,384113,211
Distribution constraints201361
Exams fixed in time57635899
Exams fixed in room24670170
Large exams (600+)22201817
Exams needing a room split1092013
Exams with original room1,5331,4851,5241,485
Density3.283%3.586%3.456%3.519%
Average periods28.145 ± 0.40928.022 ± 0.46628.152 ± 0.40627.498 ± 0.710
Average rooms262.892 ± 6.116265.771 ± 4.696256.247 ± 9.800234.674 ± 11.772
that are big enough143.300 ± 38.480143.055 ± 37.109135.087 ± 40.072126.626 ± 37.492

Problem Fall 2010 Spring 2010 Fall 2009 Spring 2009 Fall 2008
Exams2,2232,1021,9932,1672,198
with exam seating875835890794857
Students34,41830,35334,23932,21434,988
Enrollments129,090113,864125,347119,803130,539
Distribution constraints61081413
Exams fixed in time121105104161166
Exams fixed in room89109696274
Large exams (600+)2117232224
Exams needing a room split74912
Exams with original room1,9051,7991,7261,8701,849
Density2.872%3.025%3.294%2.927%2.985%
Average periods27.460 ± 0.72827.601 ± 0.66627.494 ± 0.70526.922 ± 0.98226.861 ± 1.005
Average rooms250.693 ± 5.574260.208 ± 7.252266.016 ± 5.403261.409 ± 3.817261.192 ± 4.846
that are big enough147.143 ± 33.645156.327 ± 36.201149.011 ± 36.835163.110 ± 31.800156.685 ± 34.262

In the above table, the number of examinations, students, student examination enrollments and the distribution constraints for each data set are presented. All of the datasets have 29 examination periods, all 2 hours long starting at 8 am, 10:30am, 1 pm, 3:30 pm, and 7 pm each day from Monday till Saturday, except of the last period on Saturday (at 7 pm). All four Saturday periods (8 am, 10:30am, 1 pm, and 3:30 pm) are strongly discouraged (penalty = 4), Friday afternoon periods (1 pm, 3:30 pm, and 7 pm) are discouraged (penalty = 1).

In all problems there are only a few distribution constraints and all are marked as hard (they cannot be violated). Moreover, in each problem, there are a few exams pre-assigned in time and/or room. The number of large exams, those exams for 600 or more students, is not very high either, which is good as they all should fit within the first 24 periods (excluding Saturday and the last period on Friday; the density between these exams is over 80%). There are also a few exams in each problem that need to be split into at least two rooms as there is no room big enough for the exam in its domain, either because of the number of students in the exam or due to room requirements that are put on the exam. The probability of a pair of two exams having at least one student in common is shown in the density row. The last three rows show the domain sizes of the problems, i.e., average number of available periods and rooms to an exam. The last column only counts the rooms that are big enough for the exam to fit in without the need to be split into multiple rooms. About 43% of all exams require examination (alternative) seating.

 Configurations
The following configurations were used in the MISTA 2013 experiments:
Weight production base color split
Direct Conflict1,0001,000,000-1,000,000
More Than 2 A Day10010,00010,00010,000
Back-To-Back10100100100
Period Penalty1111
Room Penalty1111
Room Split10101010
Room Split Distance0.010.010.010.01
Room Size0.0010.0010.0010.001
Room Size Factor1.11.11.11.1
Rotation Penalty0.00010.00010.00010.0001
Large Exams Weight2,500,0002,500,0002,500,0002,500,000
Room Distance0.00010.00010.00010.0001
Hard Constraint Violation--1,000-
Exam Period Split---5,000

The production configuration contains the weights as they are used in practice by the University. The base configuration gives more weight to direct student conflicts to give a better comparison with the next two configurations. In the color configuration, the graph coloring solution is used to construct an initial assignment of exams to periods and rooms and it is not allowed to create a direct conflict. To be able to do this, however, it was necessary to add the ability to break other hard constraints, namely the ability to use a prohibited period or room by an exam or to break a distribution constraint. It was still not allowed to have multiple examinations in the same room at the same period, to exceed the room capacity, or to assign an exam into more than the given maximal number of rooms.

The last configuration (named split) attempts to minimize the number of direct conflicts by adding the ability to split an exam into two. In these runs, an additional neighborhood was used (along with all the other neighborhoods mentioned above) that allowed splitting a randomly selected examination into two, assigning each in a different period, and moving students freely between these two exams if the improvement in the weighted number of student conflicts (including direct, more than two on a day, and back-to-backs) was higher than the penalization for splitting an exam Exam Period Split. If a randomly selected exam was already split, the neighborhood also tried to reshuffle the students between the two exams or merge the exams back together if the split was no longer needed (i.e., the weighted sum of student conflicts avoided by the split was smaller than the weight of the split).

 Results
The following tables contain experimental results for the first five datasets using the above four configurations (the results for the last four data sets are in the MISTA 2013 paper). The experiments were computed on an Apple MacBook Pro with a 3.06 GHz Intel Core 2 Duo processor and 8 GB RAM, running Mac OS X 10.7.3 and Java 1.6.0. In all the experiments the solver was given a time limit of two hours, and the average values of ten independent runs are shown.
production Fall 2010 Spring 2010 Fall 2009 Spring 2009 Fall 2008
Direct Conflicts 120.5 ± 2.7 112.3 ± 4.6 129.3 ± 5.0 191.7 ± 3.8 159.0 ± 4.5
More Than 2 A Day 494.3 ± 14.6 481.6 ± 12.4 455.0 ± 14.6 510.8 ± 9.2 724.8 ± 10.8
Back-To-Back 5181.5 ± 62.4 4741.6 ± 60.3 4891.8 ± 97.2 5496.1 ± 58.5 5933.7 ± 90.4
Period Preference [%] 91.1 ± 0.2 91.1 ± 0.3 90.9 ± 0.2 90.7 ± 0.2 90.2 ± 0.2
Room Preference [%] 72.4 ± 0.5 82.6 ± 0.3 72.8 ± 0.8 75.8 ± 0.4 82.3 ± 0.3
Room Distance [m] 49.3 ± 1.9 42.4 ± 3.0 54.8 ± 3.8 41.5 ± 1.5 45.0 ± 0.6
Room Split 37.8 ± 1.7 16.5 ± 3.7 28.2 ± 1.8 5.1 ± 0.9 14.4 ± 1.4
Room Split Distance [m] 116.2 ± 15.0 51.7 ± 20.0 102.5 ± 4.4 78.3 ± 40.7 210.7 ± 42.5
Room Size 52.6 ± 1.1 58.6 ± 2.1 52.0 ± 1.5 59.8 ± 1.6 51.7 ± 1.3
Rotation Penalty 12.89 ± 0.02 12.36 ± 0.04 12.37 ± 0.05 12.04 ± 0.04 12.21 ± 0.03
Large Exams Penalty 0.0 ± 0.0 0.0 ± 0.0 0.0 ± 0.0 0.0 ± 0.0 0.0 ± 0.0

base Fall 2010 Spring 2010 Fall 2009 Spring 2009 Fall 2008
Direct Conflicts 111.4 ± 1.9 79.2 ± 3.7 91.6 ± 8.1 130.3 ± 5.8 117.4 ± 4.3
More Than 2 A Day 576.9 ± 20.4 594.7 ± 16.6 619.8 ± 38.3 721.0 ± 42.8 848.1 ± 43.2
Back-To-Back 5770.8 ± 96.3 5518.5 ± 195.3 6197.7 ± 289.2 6679.7 ± 211.3 7033.9 ± 71.7
Period Preference [%] 87.3 ± 0.4 87.5 ± 0.3 88.0 ± 0.4 87.8 ± 0.2 87.5 ± 0.4
Room Preference [%] 71.4 ± 0.5 81.7 ± 0.4 71.2 ± 0.4 75.1 ± 0.3 81.9 ± 0.3
Room Distance [m] 49.8 ± 1.5 43.7 ± 1.8 57.2 ± 2.7 44.2 ± 1.1 45.1 ± 1.5
Room Split 37.1 ± 2.4 6.5 ± 1.2 31.4 ± 4.3 4.0 ± 1.3 16.8 ± 4.1
Room Split Distance [m] 119.4 ± 20.7 15.4 ± 16.8 88.2 ± 12.0 51.6 ± 30.8 144.2 ± 21.6
Room Size 50.6 ± 2.8 65.3 ± 1.6 51.4 ± 1.7 60.2 ± 2.1 51.1 ± 3.4
Rotation Penalty 13.18 ± 0.04 12.61 ± 0.05 12.61 ± 0.06 12.25 ± 0.05 12.39 ± 0.04
Large Exams Penalty 0.0 ± 0.0 0.0 ± 0.0 1.0 ± 0.0 0.0 ± 0.0 0.0 ± 0.0

color Fall 2010 Spring 2010 Fall 2009 Spring 2009 Fall 2008
Direct Conflicts 0.0 ± 0.0 0.0 ± 0.0 0.0 ± 0.0 - 0.0 ± 0.0
More Than 2 A Day 900.8 ± 23.7 1259.9 ± 33.9 1101.6 ± 43.5 - no solution - 1156.1 ± 19.1
Back-To-Back 7334.2 ± 88.5 6382.3 ± 80.8 7333.7 ± 109.4 - exists - 7652.5 ± 115.7
Period Preference [%] 86.4 ± 0.2 87.4 ± 0.3 86.1 ± 0.3 - 86.5 ± 0.4
Room Preference [%] 70.7 ± 0.8 81.5 ± 0.5 70.8 ± 0.4 - 81.6 ± 0.2
Room Distance [m] 60.1 ± 4.5 49.4 ± 2.4 65.6 ± 3.6 - 30 colors - 49.7 ± 2.0
Room Split 38.8 ± 7.4 14.9 ± 2.9 23.1 ± 3.3 - needed - 437.1 ± 21.4
Room Split Distance [m] 235.2 ± 33.3 82.1 ± 39.7 164.3 ± 36.2 - 228.8 ± 18.2
Room Size 54.5 ± 2.5 57.7 ± 2.5 55.3 ± 1.9 - 53.8 ± 2.4
Rotation Penalty 13.45 ± 0.03 12.73 ± 0.05 12.93 ± 0.04 - 12.52 ± 0.04
Large Exams Penalty 2.0 ± 0.0 0.0 ± 0.0 1.0 ± 0.0 - 2.0 ± 0.0
Unavailable Period 33.7 ± 1.4 26.7 ± 1.2 26.6 ± 1.8 - 49.5 ± 2.5
Unavailable Room 13.3 ± 1.5 10.7 ± 1.8 13.6 ± 1.3 - 4.4 ± 1.6
Violated Distribution 2.0 ± 0.0 6.5 ± 0.5 3.0 ± 0.0 - 8.1 ± 0.7

split Fall 2010 Spring 2010 Fall 2009 Spring 2009 Fall 2008
Direct Conflicts 5.0 ± 0.0 3.0 ± 0.0 1.0 ± 0.0 16.0 ± 0.0 3.0 ± 0.0
More Than 2 A Day 124.2 ± 20.2 132.3 ± 11.7 80.9 ± 11.9 108.0 ± 18.9 131.8 ± 16.8
Back-To-Back 2117.6 ± 106.7 2141.4 ± 139.5 1707.3 ± 94.6 1959.7 ± 148.3 2046.8 ± 89.8
Period Splits 95.90 ± 6.56 90.50 ± 4.45 94.20 ± 2.35 105.40 ± 5.44 113.90 ± 3.70
Period Preference [%] 87.8 ± 0.2 87.5 ± 0.3 88.1 ± 0.4 87.8 ± 0.5 88.2 ± 0.5
Room Preference [%] 69.3 ± 0.8 81.2 ± 0.2 70.5 ± 0.4 72.1 ± 5.2 81.1 ± 0.4
Room Distance [m] 56.2 ± 2.2 46.1 ± 1.8 59.7 ± 2.4 55.5 ± 20.7 49.2 ± 1.5
Room Split 43.4 ± 10.3 9.5 ± 3.6 26.8 ± 7.9 13.4 ± 6.3 20.6 ± 3.8
Room Split Distance [m] 95.6 ± 16.6 54.9 ± 29.6 65.9 ± 29.5 135.3 ± 28.1 105.6 ± 46.3
Room Size 63.1 ± 2.7 72.7 ± 2.1 70.4 ± 2.4 73.5 ± 13.6 63.1 ± 4.2
Rotation Penalty 13.19 ± 0.05 12.60 ± 0.03 12.62 ± 0.03 12.40 ± 0.12 12.32 ± 0.07
Large Exams Penalty 0.0 ± 0.0 0.0 ± 0.0 0.0 ± 0.0 0.0 ± 0.0 0.0 ± 0.0

Any of the above experiments can be reproduced using the CPSolver library:
`java -Xmx2g -cp cpsolver-1.3.jar org.cpsolver.exam.Test \   exam-production_v13.cfg pu-exam-fal12.xml pu-exam-fal12-s.xml`
where `exam-production_v13.cfg` is one of the above four configurations, `pu-exam-fal12.xml` is an input problem and `pu-exam-fal12-s.xml` is the resulting solution.