Another strategy we explored was simulated annealing.
Simulated annealing models the physical process of shaping metal while it is cooling. We start with an initial temperature of the system t, and decrease it as the number of iterations increases. Each iteration, there is a random swap of students and classes, and we accept a given swap with probability p, which uses the current temperature of the system.
The longer the process has been going for, the less likely we are to accept large changes that would move us away from an optimum (head downhill).
Because we sometimes accept moves (student/class swaps) that might lower our total utility, we have the ability to get out from being stuck in a local optima and work toward a larger local optima or global optima.
There are drawbacks to applying this method at scale over others. We did see an improvement in total utility by applying this algorithm, but know that with further research and tuning of parameters there is still room for further improvement. The course allocation problem's complexity does pose extra difficulty for simulated annealing. For a given state of the problem, there is a large number of potential successor states. While simulated annealing chooses one of these at random, the sheer number of possibilities means that the chance of randomly choosing a beneficial successor state could be small.
Running the simulated annealing program for real-life scaled data would be computationally intensive. Additionally, this method doesn’t know whether its found the global optima, we just run it for long enough by setting a really high initial temperature that it can (or probably will) find the global optima.
Our implementation of simulated annealing may be found in our Github repo.