Course Exam Scheduling

Course Exam Scheduling is a timetabling problem in which a university assigns its final exams to a fixed set of exam time slots so as to minimize the burden on students, such as back-to-back exams, three exams within one day, or three exams within 24 hours. Cornell University schedules its exams with the Group-then-Sequence (GtS) framework [Ye26]: exams are first grouped into blocks (block assignment), the blocks are then sequenced into time slots (block sequencing), and a local search can further improve the schedule (post-processing). The block assignment can be conflict-free, so that no student has two exams in the same block, or a minimum-conflict assignment, which minimizes the number of such conflicts but may not eliminate them. The benchmark instances represent only the Block Sequencing subproblem, not the complete GtS scheduling framework: given a block assignment, the blocks are sequenced into time slots to minimize a weighted count of undesirable exam patterns, computed from the pairwise and triplet student co-enrollment between blocks.

Formally, we are given a set of blocks \(B=\{1,\dots,n\}\) and an equal number of consecutive exam slots \(S=\{1,\dots,n\}\), three slots per day (morning, afternoon, evening). The successor of slot \(s\) is \(\sigma(s)=s+1\) for \(s\lt n\) and \(\sigma(n)=1\), so the sequence wraps around cyclically. We are also given the pairwise co-enrollment \(p_{ij}\) (number of students with exams in both blocks \(i\) and \(j\)), the triplet co-enrollment \(t_{ijk}\) for blocks \(i,j,k\), and penalty weights \(\alpha,\beta,\gamma,\delta\geq 0\). A penalized pattern can start at the following slots: \(S_{EM}=\{s\leq n-1: s \bmod 3=0\}\) (evening followed by next morning), \(S_{BB}=\{s\leq n-1: s \bmod 3\neq 0\}\) (other back-to-back slots), \(S_{TD}=\{s\leq n-2: s \bmod 3=1\}\) (three slots in the same day), \(S_{T24}=\{s\leq n-2: s \bmod 3\neq 1\}\) (three slots within 24 hours), and \(S_{T}=S_{TD}\cup S_{T24}=\{1,\dots,n-2\}\).

We want to assign every block to exactly one slot, with every slot holding exactly one block, so as to minimize the weighted number of students affected by each pattern. Variables:

• \(x_{ijks}\in\{0,1\}\): blocks \(i,j,k\) are placed in slots \(s,\sigma(s),\sigma(\sigma(s))\);
• \(y_{ijk}\in\{0,1\}\): the sequence \(i,j,k\) starts at a slot in \(S_T\);
• \(z_{ijkl}\in\{0,1\}\): the four-block sequence \(i,j,k,l\) occurs (both \(i,j,k\) and \(j,k,l\) start in \(S_T\));
• integer \(TD, T24, EM, BB, F\geq 0\): the number of students with three exams in one day, three exams within 24 hours, back-to-back exams from evening to the next morning, other back-to-back exams, and three exams within four consecutive slots;
• schedule-recording variables that do not enter the objective: \(b_{is}\in\{0,1\}\) (block \(i\) is in slot \(s\)), integer \(a_i\geq 0\) (slot of block \(i\)), integer \(q_s\geq 0\) (index of the block in slot \(s\)), integer \(d_{ij}\geq 0\) (at least the slot distance between blocks \(i\) and \(j\)), and \(L_{ij}\in\{0,1\}\) (blocks \(i\) and \(j\) are at least 16 slots apart).

Below is the block sequencing MILP formulation of [Ye26] as used in the instances of [Cai26], with \(\alpha=10\), \(\beta=5\), \(\gamma=3\), \(\delta=2\). These weights are benchmark-specific choices following [Cai26] and differ from those in [Ye26]. The original formulation of [Ye26] also distinguishes two types of back-to-back penalties, with a weight \(\gamma_1\) for evening-to-morning back-to-back exams and a weight \(\gamma_2\) for other back-to-back exams; the benchmark instances use a single weight \(\gamma=\gamma_1=\gamma_2\) for both.

\begin{align} &\min\;\alpha\, TD+\beta\, T24+\gamma\,(EM+BB)+\delta\, F&\nonumber\\ &\sum_{j\in B}\sum_{k\in B}\sum_{s\in S}x_{ijks}=1&\forall i\in B\\ &\sum_{i\in B}\sum_{k\in B}\sum_{s\in S}x_{ijks}=1&\forall j\in B\\ &\sum_{i\in B}\sum_{j\in B}\sum_{s\in S}x_{ijks}=1&\forall k\in B\\ &\sum_{i\in B}\sum_{j\in B}\sum_{k\in B}x_{ijks}=1&\forall s\in S\\ &x_{iiks}=x_{ijis}=x_{ijjs}=0&\forall i,j,k\in B,\ s\in S\\ &\sum_{i\in B}x_{ijks}=\sum_{l\in B}x_{jkl\sigma(s)}&\forall j,k\in B,\ s\in S\\ &y_{ijk}=\sum_{s\in S_T}x_{ijks}&\forall i,j,k\in B\\ &z_{ijkl}\geq y_{ijk}+y_{jkl}-1&\forall i,j,k,l\in B\\ &TD=\sum_{i,j,k\in B}\sum_{s\in S_{TD}}t_{ijk}\,x_{ijks}&\\ &T24=\sum_{i,j,k\in B}\sum_{s\in S_{T24}}t_{ijk}\,x_{ijks}&\\ &EM=\sum_{i,j,k\in B}\sum_{s\in S_{EM}}p_{ij}\,x_{ijks}&\\ &BB=\sum_{i,j,k\in B}\sum_{s\in S_{BB}}p_{ij}\,x_{ijks}&\\ &F=\sum_{i,j,k,l\in B}(t_{ijl}+t_{ikl})\,z_{ijkl}&\\ &q_s=\sum_{i,j,k\in B}i\,x_{ijks}&\forall s\in S\\ &b_{is}=\sum_{j\in B}\sum_{k\in B}x_{ijks}&\forall i\in B,\ s\in S\\ &a_i=\sum_{s\in S}s\,b_{is}&\forall i\in B\\ &d_{ij}\geq a_i-a_j,\quad d_{ij}\geq a_j-a_i&\forall i,j\in B\\ &16\,L_{ij}\leq d_{ij}\leq 15+20\,L_{ij}&\forall i,j\in B\\ &x_{ijks},\,y_{ijk},\,z_{ijkl},\,b_{is},\,L_{ij}\in\{0,1\}&\\ &q_s,\,a_i,\,d_{ij},\,TD,\,T24,\,EM,\,BB,\,F\in\mathbb{Z}_{\geq 0}& \end{align}

The instances have \(n=12\) (Hard) and \(n=14\) (Hard2) blocks and slots. Then \(d_{ij}\leq n-1\lt 16\) for any schedule, so constraint (18) forces \(L_{ij}=0\) and does not restrict the schedule. An instance has \(2n^4+n^3+2n^2\) binary variables, \(n^2+2n+5\) general integer variables, and \(n^4+5n^3+5n^2+6n+5\) constraints.

@misc{huang2024distributional,
      title={Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods}, 
      author={Weimin Huang and Taoan Huang and Aaron M Ferber and Bistra Dilkina},
      year={2024},
      eprint={2406.06954},
      archivePrefix={arXiv},
      primaryClass={cs.LG}
}

@article{ye2026cornell,
  title={Cornell University uses integer programming to optimize final exam scheduling},
  author={Ye, Tinghan and Jovine, Adam S and Van Osselaer, Willem and Zhu, Qihan and Shmoys, David B},
  journal={INFORMS Journal on Applied Analytics},
  volume={56},
  number={2},
  pages={159--177},
  year={2026},
  publisher={INFORMS}
}