Constraint-Based Exam Scheduling with Mathematical Optimization

Overview

Exam scheduling appears straightforward until you consider the constraints. Students cannot take two exams at the same time. Certain courses need early slots. Some exams require specific rooms. The number of possible arrangements grows exponentially with each additional course and student.

This article shows how to model exam scheduling as a mathematical optimization problem. We formulate the constraints using linear algebra, then let solvers find valid solutions automatically.

The Problem

Consider a university with hundreds of courses, thousands of students, and limited time slots. Each student enrolls in a unique combination of courses, creating complex overlap patterns. The core constraint is simple: no student should have conflicting exams. But applied across thousands of enrollments, this creates an intricate dependency graph that's nearly impossible to solve manually.

Mathematical Foundation

Linear Programming is an optimization framework where both the objective function and constraints are linear. A standard form looks like:

$$\min \quad c^T x$$ $$\text{s.t.} \quad Ax = b, \quad x \geq 0$$

For exam scheduling, we extend this to 0-1 Integer Programming where decision variables are binary.

The Model

Decision Variables

We define a binary matrix $X = [x_{ij}]$ where:

$$x_{ij} = \begin{cases} 1 & \text{if course } i \text{ is scheduled in time slot } j \\ 0 & \text{otherwise} \end{cases}$$

For $n$ courses and $m$ time slots, $X$ has shape $(n \times m)$.

Enrollment Matrix

We capture student enrollments in matrix $A = [a_{ik}]$ where:

$$a_{ik} = \begin{cases} 1 & \text{if student } k \text{ is enrolled in course } i \\ 0 & \text{otherwise} \end{cases}$$

For $n$ courses and $s$ students, $A$ has shape $(n \times s)$.

Constraints

Constraint 1: Each course scheduled exactly once

Every course must appear in exactly one time slot:

$$\sum_{j=1}^{m} x_{ij} = 1 \quad \forall i \in \{1, ..., n\}$$

In matrix form with $\mathbf{1}_m$ as a column vector of ones:

$$X \cdot \mathbf{1}_m = \mathbf{1}_n$$

Constraint 2: No student conflicts

For each time slot, each student can have at most one exam. The product $X^T A$ gives us a $(m \times s)$ matrix where entry $(j, k)$ represents how many exams student $k$ has in slot $j$. This must not exceed 1:

$$X^T A \leq \mathbf{1}_{m \times s}$$

Example

Suppose we have 2 courses, 7 students, and 3 time slots.

Enrollment matrix $A$ (which students take which courses):

$$A = \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 \end{bmatrix}$$

Row 1: Course 1 is taken by students 1, 3, 5, 7. Row 2: Course 2 is taken by students 1, 2, 3, 7.

Decision variable matrix $X$:

$$X = \begin{bmatrix} x_{1,1} & x_{1,2} & x_{1,3} \\ x_{2,1} & x_{2,2} & x_{2,3} \end{bmatrix}$$

Applying Constraint 1 (each course once):

$$\begin{bmatrix} x_{1,1} + x_{1,2} + x_{1,3} \\ x_{2,1} + x_{2,2} + x_{2,3} \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$$

Applying Constraint 2 (no conflicts):

$$X^T A = \begin{bmatrix} x_{1,1} & x_{2,1} \\ x_{1,2} & x_{2,2} \\ x_{1,3} & x_{2,3} \end{bmatrix} \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 \end{bmatrix} \leq \mathbf{1}_{3 \times 7}$$

Students 1, 3, and 7 take both courses, so their columns will show conflicts if both courses land in the same slot.

Objective Functions

Beyond finding any feasible solution, we can optimize for preferences:

Schedule certain courses early:

$$\min \sum_{i \in S} \sum_{j=1}^{m} j \cdot x_{ij}$$

where $S$ is the set of courses to prioritize.

Spread exams evenly by minimizing maximum load per slot, or add soft constraints penalizing consecutive exams for students.

Implementation

def create_exam_schedule(enrollment_matrix, num_slots):
    n_courses, n_students = enrollment_matrix.shape

    model = OptimizationModel()

    # Decision variables: X[i,j] = 1 if course i in slot j
    X = model.add_binary_vars(n_courses, num_slots)

    # Constraint 1: each course in exactly one slot
    for i in range(n_courses):
        model.add_constraint(sum(X[i, :]) == 1)

    # Constraint 2: no student conflicts (X^T @ A <= 1)
    for j in range(num_slots):
        for k in range(n_students):
            conflict_count = sum(
                X[i, j] * enrollment_matrix[i, k]
                for i in range(n_courses)
            )
            model.add_constraint(conflict_count <= 1)

    model.solve()

    # Extract schedule
    schedule = {}
    for i in range(n_courses):
        for j in range(num_slots):
            if X[i, j].value == 1:
                schedule[i] = j

    return schedule

The Value

This mathematical approach transforms scheduling from guesswork into a systematic process. The solver explores the solution space efficiently, finding valid schedules in minutes even for large instances. When constraints change, simply update the model and re-solve.

The matrix formulation scales naturally. Whether scheduling 50 courses or 500, the same mathematical structure applies. Constraints that humans cannot track mentally, like ensuring no student has three exams in 24 hours, become straightforward additions to the model.