Purdue Final Examination Data Sets

• Problem Description
• Data Format

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.

• Fall 2008 [pu-exam-fal08]
• Spring 2009 [pu-exam-spr09]
• Fall 2009 [pu-exam-fal09]
• Spring 2010 [pu-exam-spr10]
• Fall 2010 [pu-exam-fal10]
• Spring 20101[pu-exam-spr11]
• Fall 2011 [pu-exam-fal11]
• Spring 2012 [pu-exam-spr12]
• Fall 2012 [pu-exam-fal12]

Download all nine data sets in one zip file here.

Problem Characteristics

The data sets have the following properties:

Problem	Fall 2012	Spring 2012	Fall 2011	Spring 2011
Exams	1,864	1,798	1,914	1,866
with exam seating	819	780	827	801
Students	33,279	31,593	33,856	31,688
Enrollments	117,265	111,345	122,384	113,211
Distribution constraints	20	13	6	1
Exams fixed in time	57	63	58	99
Exams fixed in room	24	6	70	170
Large exams (600+)	22	20	18	17
Exams needing a room split	10	9	20	13
Exams with original room	1,533	1,485	1,524	1,485
Density	3.283%	3.586%	3.456%	3.519%
Average periods	28.145 ± 0.409	28.022 ± 0.466	28.152 ± 0.406	27.498 ± 0.710
Average rooms	262.892 ± 6.116	265.771 ± 4.696	256.247 ± 9.800	234.674 ± 11.772
that are big enough	143.300 ± 38.480	143.055 ± 37.109	135.087 ± 40.072	126.626 ± 37.492
Problem	Fall 2010	Spring 2010	Fall 2009	Spring 2009	Fall 2008
Exams	2,223	2,102	1,993	2,167	2,198
with exam seating	875	835	890	794	857
Students	34,418	30,353	34,239	32,214	34,988
Enrollments	129,090	113,864	125,347	119,803	130,539
Distribution constraints	6	10	8	14	13
Exams fixed in time	121	105	104	161	166
Exams fixed in room	89	109	69	62	74
Large exams (600+)	21	17	23	22	24
Exams needing a room split	7	4	9	1	2
Exams with original room	1,905	1,799	1,726	1,870	1,849
Density	2.872%	3.025%	3.294%	2.927%	2.985%
Average periods	27.460 ± 0.728	27.601 ± 0.666	27.494 ± 0.705	26.922 ± 0.982	26.861 ± 1.005
Average rooms	250.693 ± 5.574	260.208 ± 7.252	266.016 ± 5.403	261.409 ± 3.817	261.192 ± 4.846
that are big enough	147.143 ± 33.645	156.327 ± 36.201	149.011 ± 36.835	163.110 ± 31.800	156.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 Conflict	1,000	1,000,000	-	1,000,000
More Than 2 A Day	100	10,000	10,000	10,000
Back-To-Back	10	100	100	100
Period Penalty	1	1	1	1
Room Penalty	1	1	1	1
Room Split	10	10	10	10
Room Split Distance	0.01	0.01	0.01	0.01
Room Size	0.001	0.001	0.001	0.001
Room Size Factor	1.1	1.1	1.1	1.1
Rotation Penalty	0.0001	0.0001	0.0001	0.0001
Large Exams Weight	2,500,000	2,500,000	2,500,000	2,500,000
Room Distance	0.0001	0.0001	0.0001	0.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.