A simulated annealing approach to the student-project allocation problem
  We describe a solution to the student-project allocation problem using
simulated annealing. The problem involves assigning students to projects, where
each student has ranked a fixed number of projects in order of preference. Each
project is offered by a specific supervisor (or supervisors), and the goal is
to find an optimal matching of students to projects taking into account the
students' preferences, the constraint that only one student can be assigned to
a given project, and the constraint that supervisors have a maximum workload.
We show that when applied to a real dataset from a university physics
department, simulated annealing allows the rapid determination of high quality
solutions to this allocation problem. The quality of the solution is quantified
by a satisfaction metric derived from empirical student survey data. Our
approach provides high quality allocations in a matter of minutes that are as
good as those found previously by the course organizer using a laborious
trial-and-error approach. We investigate how the quality of the allocation is
affected by the ratio of the number of projects offered to the number of
students and the number of projects ranked by each student. We briefly discuss
how our approach can be generalized to include other types of constraints and
discuss its potential applicability to wider allocation problems.
