Randomness for Allocation Problems

I have a younger sibling who is a primary school student. With the end of the school year fast approaching, she and her classmates were issued a form to complete, allowing them to specify who they would like to be placed in a class with next year. The form offered three preferences: a first, second and a third choice, where you were most likely to be placed in a class with your first choice, although none of them were guaranteed.

After the teachers had rounded up the dozens of paper scraps from the children, they set some time aside to figure out a class allocation that made everybody happy. Reportedly, this took a collective effort worth 7 hours. By some accounts, the new allocation of students to classes was a massive success – many students were pleased to report that they were with all three of their chosen classmates. However, there were also many students who, unfortunately, were not given a place with any of their choices.

Firstly, it shocked me to learn that the teachers were calculating the allocation manually. They all sat down and, having looked at the preferences from each pupil, figured out among themselves who was in which class. Secondly, it shocked me to learn how tremendously bad humans are at solving these sorts of problems. It doesn’t immediately seem fair that some of the students get to be with all of their choices while some get to be with none at all. To me, this seemed unbalanced: wouldn’t it be far better to make sure everyone is with at least one of their choices, and treat them being with more than one as an added benefit? Was such an arrangement even possible?

There had to be an automated way to do this. My immediate thought was to use a genetic algorithm to find a good allocation, so I threw together some code and made a project proposal for the school. Turns out, they were really excited about the project and would love to trial a piece of software that does the heavy lifting for them. Over the past week or two, I’ve been working on a program for the school that allows for the forms to be filled out online, and a near-optimal allocation to be found automatically using numerous machine learning techniques.

This post is to document my progress and ideas.

What Kind of Problem Are We Dealing With?

(spoiler alert: a computationally hard one)

Allocations such as this are textbook examples of optimisation problems. The general idea is that, from a group of feasible solutions, we want to find the best one. With no idea of how many students were in each year group or how many classes they were divided down into, I made the sensible assumption that there were a total of 90 pupils, divided down into three classes of roughly 30.

For the mathematically inclined, you’ll probably have already realised the scale of the problem we’re dealing with. Three classes of 30, only 90 students – how hard can it be to find the best allocation? … Okay, probably quite hard, but definitely something we can calculate with a computer, right?

Wrong. The problem is intractable. There exists no known solutions which can solve this problem in polynomial time, meaning that for all but the smallest scales, problems like this are far, far beyond the reach of solution by computers, no matter how powerful they are.

This is quite sobering. Something where it seems trivial to find an optimal solution, such as putting students with their friends in their classes, is pretty much impossible for a year group of any reasonable size.

Let’s give the scale of the problem some cardinality. We’re going to make use of the binomial coefficient extensively here, so if you’re unsure on what that is, have a look at that link. Again – we have 90 students, split into groups of 30 among three classes. How many unique allocations of students to classes are there? There are \(\binom{90}{30} \approx 6.7 \times 10^{23}\) ways to choose the first 30 people, and \(\binom{60}{30} \approx 1.2 \times 10^{17}\) ways to choose the next 30. Of course, at this point, there are only 30 students left, so there is only one combination to speak of – you can verify this with the binomial coefficient, \(\binom{30}{30} = 1\).

Therefore, to find the total number of allocations, we multiply these numbers together. \(\binom{90}{30} \times\binom{60}{30} \times\binom{30}{30}\), which works out at around \(8 \times 10^{40}\). Note that this number is sensitive to the order of the classes – for example, {class a}{class b}{class c} and {class b}{class c}{class a} are two different allocations as far as this value is concerned. To cancel this out, we simply divide the number by the number of permutations of a list of 3 values, given as \(3! = 3 \times 2 = 6\). Dividing the number by 6 gives \(1.3 \times 10^{40}\).

Seeing the number written in scientific notation definitely does not do it justice. That number is 41 decimal digits long. It absolutely dwarfs the number of cells in our bodies. As a matter of fact, it’s more than the number of human cells on this planet right now. It is so large that, if you were to reanimate every single human being who ever existed human being who ever existed and count every single one of their cells, it’d still be larger than that by a factor of \(10^{15}\).

Let’s assume that you have a computer that can create and gauge the quality of one billion allocations every nanosecond. That means your computer can conjure up \(1.0 \times 10^{18}\) allocations per second. Therefore, it’ll take \(\frac{1.3 \times 10^{40}}{1.0 \times 10^{18}} \approx 1.3 \times 10^{22}\) seconds to guarantee it’ll find the optimal solution. That’s 32 billion years – ~2.5 times longer than the Universe has existed.

We simply cannot find the optimal solution. It is completely out of reach for us, and will likely remain so. However, all is not lost. In situations like these, if we are willing to settle for a solution which is ‘good enough’, even the computationally impossible problems can be tamed with the right technique. And as it turns out, a dose of randomness and relaxation works wonders for this problem in particular.

A Dose of Randomness

Computer algorithms are often thought of as being “deterministic”. They follow one step from another in exactly the same way every single time. In other words, nothing is left to chance and the algorithm proceeds exactly as programmed with no behavioural fluctuations. The output of a deterministic algorithm is always the same for any given input.

This property is critical in many domains. For example, a cryptographic hash function is deterministic by necessity. Deterministic algorithms produce useful, reproducible results in a reliable way, so why would we settle for anything less?

As it turns out, behavioural fluctuations and randomness in computer software is mysteriously effective. Flipping a metaphorical coin a few times goes a long way for finding near-optimal solutions to optimisation problems in significantly less time than the deterministic alternative.

Who knows why. Michael Rabin, perhaps most accredited for his major contributions to the Miller-Rabin primality test, says (source):

I must admit that after many years of work in this area, the efficacy of randomness for so many algorithmic problems is absolutely mysterious to me. It is efficient, it works; but why and how is absolutely mysterious.

The Techniques

The program makes uses of a few interesting techniques to find a near-optimal class allocation solution. As it currently stands, I’m far from satisfied, even though the algorithm capably produces some viable solutions to the problem. The algorithm incorporates elements from a number of different optimisation methods, namely:

  • Shotgun hill climbing. A variant on regular hill climbing, SHC avoids getting stuck in local maxima by randomising the initial configuration every so often.
  • Hill climbing jitter. For some reason, unbeknownst to me, adding random variations into the hill climbing algorithm, such as moving towards less favourable solutions occasionally, produces drastically preferable results. Introducing jitter enables us to find a global maximum much more effectively.
  • Genetic algorithms. The class arrangement is encoded into a 1D data structure, which we randomly mutate in each generation to yield some successors. By analysing each arrangement for favourability using a fitness function, we can eliminate weak strains in a ‘survival of the fittest’-type scenario, as in nature. With enough generations, the algorithm yields a selection of favourable plans.

I’m not going to dwell on how the algorithm works at this early stage, since I’m still working on optimising it and making it as efficient as it can be. That’s probably going to be for another post. Besides, I might discover some better way of working the entire thing.

Before I’m finished with the project I want to test implementations involving optimisation algorithms like the Metropolis algorithm and simulated annealing.

It might be worth mentioning that the program was designed to use a client-server architecture for this very reason. The client is what the teachers use to view and modify the students preferences, and to prime the data before it is sent off to find an optimal configuration, whereas the server is what actually does the heavy lifting and finds a good allocation. I chose to do this for three reasons:

  • The algorithm is computationally intensive. It’s more reliable and is quicker to run it on a dedicated server.
  • If further optimisations need to be made on the algorithm after deployment (or even while the school is experimenting with the prototype), it can be done silently without having to modify the client software installed on school systems.
  • The client computer doesn’t have to be on while the server is computing an allocation. For example, you could set the algorithm running for 24 hours to find a really good solution and it wouldn’t matter what the client computer is doing. It could be turned off, for all the server cares.

Optimisation Objectives

The objectives I’m currently accounting for in the optimisation algorithm are listed below:

  • Student preferences. This is the most important thing as far as our algorithm is concerned. We favour placing students with their choices before any other objectives since this is what the program is designed to do.
  • Student ability. For each of the students’ subjects, they can be assigned a value from \(0\) to \(N\) representing how capable they are in that subject. We favour placing the more capable students with perhaps struggling students, since hopefully they will teach one another and encourage a more positive atmosphere in the classroom.

I might find some more interesting objectives to account for before I finish the project. Any ideas, let me know!

Written on August 18, 2017