October 2014

Part toy project, past solution for a friend, this project looked at using computational power to solve a difficult problem, otherwise left to a human.

My girlfriend is a Doctor and asked me one day if I could solve the problem of work Doctors’ work rotas, which are still compiled manually by humans, poring over all the various constraints and requests for holiday by every member of every department, and usually resulting in a largely unsatisfactory result.

A little research into the NP-hard problem satisfied me that the answer wasn’t trivial, but some headway could be made using the field of heuristic search algorithms. While these techniques do not promise to come up with the optimal solution to a problem, for the right use cases, they do tend to come up with a very good solution, in a very reasonable space of time.

I wrote this simulated annealing algorithm in R in order to solve a parallel problem to work rotas; (albeit one that is slightly easier to phrase in linear algebra). This script finds a good seating plan for an event (e.g. a wedding or party), based on each attendees preference for sitting with each other attendee.

Please take a look at my blog post for more information on the analytics in use.