Application of Graph Theory in Final Exam Scheduling for Cornell Students
Since last year, I have been involved in the Final Exam Scheduling Team under the ORIE Undergraduate Research Society as a research assistant. With ORIE’s focus on optimization and finding the most feasible solution given some constraints, the Final Exam Scheduling Team’s goal is to optimize the final exam schedule to lessen students’ burdens and grant them more time flexibility.
The Cornell Office of the University of Registrar maintains some policies regarding final exams, such that there are 2-3 exams slots per day for 7 days and that a student can’t have more than two exams within 24 hours. Our team receives the course enrollment data of around 21,000 undergraduate students after the add-drop period and only considers classes with the standard 2 hours and 30 minutes final exams.
Given an .xlsx file of around 50,000 records (each enrollment in a course is one row), we first transform the data into a graph to figure out which exams should be in the same exam slot before adopting more complicated combinatorial optimization methods. A graphical representation of the data helps divide the exams into 19 blocks. Each node is a class, each edge connecting 2 exams is the co-enrolled students, and the weight of an edge is the number of students co-enrolled in 2 exams.
The graph is undirected, as there isn’t really a direction when describing the number of co-enrolled students. When dividing the exams into 19 blocks, we take a look at the pair of 2 nodes with the weakest ties, as it would be best to group exams that have the least number of students co-enrolled to have as few make-up exams as possible.
While there are definitely other ways to represent the data (i.e. matrix), the graph has been very useful for our team in the intermediary steps. For example, in the post-processing step where we try to reduce the number of back-to-back exams, we adopt a local search algorithm by identifying an exam that’s causing a lot of back-to-backs, checking how many back-to-back exams that would cause through the weights of the edges, and moving the exam to the slot where it would cause the least number of back-to-backs. We complete the first step by measuring the influence of each node (exams)–by computing how many connected components there would be if it was removed from the graph, which was very similar to our first question in the problem set.
With its defining characteristics of simplifying a complex model into a more abstract form to observe what we’re looking for, I thought of this project as a perfect real-world application of graph theory. We actually just got the student enrollment data from the Registrar now that the add period has passed, and our team is very excited to adopt the integer program for this semester! Feel free to read the attached poster for more technical details.
Source:
https://drive.google.com/file/d/1b3D60i91hIpEcIrWB5jRg_VwUJTE__Yb/view?usp=sharing