How we assign students to tutorials

Rather than using a first-come-first-served or manual assignment process, we use convex optimization to compute an optimal assignment that minimizes total dissatisfaction, subject to tutorial capacity constraints. This guarantees

• global optimality: finds the best possible assignment considering everyone’s preferences simultaneously;
• fairness: no advantage to submitting preferences early; all students treated equally;
• transparency: the algorithm and objective function are well-defined and verifiable.

Mathematical Formulation

We formulate the tutorial assignment problem as a binary integer linear program (BILP).

Objective

Let:

• \(n\): number of students
• \(m\) = number of tutorial slots
• \(\cF_i\) = set of tutorials in student \(i\)’s preference list (up to 5 choices)

Define binary decision variables \(x_{i,j} \in \{0, 1\}\), \(j \in\cF_i\), \(i \in [n]\triangleq \{1, \dots, n\}\), where \(x_{i,j} = 1\) if student \(i\) is assigned to tutorial \(j\), and \(x_{i,j} = 0\) otherwise.

We associate each preference rank with a dissatisfaction level:

• 1st choice: no dissatisfaction (0)
• 2nd choice: 1
• 3rd choice: 2
• 4th choice: 3
• 5th choice: 4

Let \(c_{i,j}\) denote the dissatisfcation of assigning student \(i\) to tutorial \(j\). We minimize the total dissatisfaction:

This objective prioritizes giving students their higher-ranked choices while keeping the assignment feasible (ie respecting tutorial capacity constraints). Minimizing total dissatisfaction is a natural choice because it:

• treats all students exchangeably
• has a clear interpretation
• is computationally tractable to minimize

The linear dissatisfaction structure implicitly assumes that each step down in preference rank incurs an equal increase in dissatisfaction; ie the increase in dissatisfication from 1st→2nd choice equals the increase in dissatisfaction from 2nd→3rd, 3rd→4th, etc.

Here are some alternative formulations we considered (but ultimately decided against):

• non-linear dissatisfaction structures: exponential (assigning a student to their k-th choice incurrs \(2^k\) dissatisfication), quadratic (assigning a student to their k-th choice incurrs \(k^2\) dissatisfaction), or other dissatisfaction structures. This introduces subjectivity to the assignment mechanism (which dissatisfiaction structure to use?).
• lexicographic assignment mechanism: maximize the number of 1st choices assignments, then maximize the number of 2nd choices assignments, etc. This requires solving multiple optimizations, and can lead to unstable assignments (small changes in student preferences lead to large changes in assignment).
• minimax assignment mechanism: minimize worst-case individual dissatisfaction. This may be overly conservative; ie, we may increase dissatisfaction of many students to reduce the dissatisfiaction of one hard-to-satisfy student

Constraints

Assignment constraint: Each student must be assigned to exactly one tutorial:

Capacity constraint: The number of students assigned to each tutorial cannot exceed its capacity:

We put the objective and constraints together to obtain the BILP:

While BILPs are generally NP-hard, this particular problem can be solved efficiently because it has an exact convex relaxation.

LP Relaxation: Consider replacing the integer constraints \(x_{i,j} \in \{0,1\}\) to continuous constraints \(x_{i,j} \in [0,1]\). This converts the BILP into a linear program (LP), which can be solved efficiently with interior-point or simplex methods. This conversion is called relaxation because the new constraints are less restrictive thatn the old constraints; ie, the new constraints are “relaxed” versions of the old constraints. Instead of solving the original BILP, we solve the LP relaxation of the BILP because there are efficient algorithms to solve LPs (not the case for BILPs).

The main issue with solving convex relaxations instead of the original problem is optimal solutions to the convex relaxation may not be satisfy the original constraints (eg, optimal solutions to the LP relaxations of BILPs may not be integer-valued). When we relax constraints, we may introduce new feasible points that achieve smaller objective values than the optimal (objective) value of the original problem. If this occurs, then solving the convex relaxation does not help us solve the original problem because the optimal solution of the convex relaxation will be among the new feasible points introduced by relaxation.

Remarkably, for the tutorial assignment problem, the LP relaxation has integer-valued optimal solutions; ie the optimal solution of the LP relaxation also satisfies the original integrality constraints! Thus we can solve the BILP exactly by solving its LP relaxation! This occurs because constraint matrix has a special structure:

• Students on one side, tutorials on the other (bipartite graph)
• Each student chooses exactly one tutorial: \(\sum_j x_{i,j} = 1\)
• Each tutorial has a capacity limit: \(\sum_i x_{i,j} \leq \text{cap}_j\)

This constraint structure forms a network flow matrix, which is totally unimodular: every square submatrix has determinant in \(\{-1, 0, +1\}\).

Total Unimodularity Theorem: If the constraint matrix \(A\) is totally unimodular and the right-hand side vector \(b\) is integer-valued, then every basic feasible solution to the LP is automatically integer-valued.

Since our capacity constraints have integer right-hand sides (5, 10, 15, etc.), all vertices of the LP polytope are integer points. Therefore, any LP solver will return an integer-valued optimal solution without requiring specialized integer programming heuristics. Further, since the LP solver searched over a larger feasible set than the original BILP feasible set, the (integer-valued) optimal solution from the LP solver is guaranteed to optimal for the BILP.

Results

For the winter 2026 offering of STATS 413, we assigned 166 students to 24 tutorials with capacities ranging from 5 to 25 students. The table below breaks down the assignments made by the LP relaxation.

January 11, 2026