Today my friend Alan came to me with a problem: “Suppose you have 100 students in a math seminar and you to give two books to each student as the seminar ends. Furthermore, each ranks all the available books. The question is, how do you find an efficient way of distributing the books so that overall ‘happiness’ is maximized”. Also, you want to have a sense of “fairness” so that no student gets screwed over with two books that he didn’t want at all.
During the past four years, the seminar in which I work at has proceeded to solve this problem by manually assigning books to kids and hopefully, after many hours of tedious work, get to a distribution that is reasonable. Alan and I decided that there had to be a better way and started to think on a systematic solution for this problem. After a while of thinking, it came to me. This problem could be though as a Linear Program! – meaning that it could be solved using a standard algorithm, the simplex algorithm (used heavily in hedge funds, operation research and many other fields). Somehow after almost failing 6.046 – the de facto algorithms class at MIT – I was thinking about this problem without all the pressure of a grade using what I had learned and was enjoying it a lot.
The interesting part is that, not only were we dedicated to solve this problem using an algorithmic solution, but we were also competing to see if it was worth it. Wendy, another staff member, was not too much a fan of our approach. Instead, she decided to attempt solving the problem once again, manually. In order to compare which of the two approaches was best, we set the following rules of comparison: we would compare the total time it would take to solve the problem 5 years in a row (the seminar happens annually). What this means is that we would take whatever time it took Wendy to solve the problem manually and multiply it by five. However, for our approach, we would consider the time it took us to come up with a solution and add it to five times the time it would take a computer to execute the code. The idea was that, once the code was developed it could be reused as is in the following years.
We spent part of the night brainstorming, learning about .mps (an extremely old file format inspired by punch cards that apparently is used as a standard input for Linear Program solvers), looking for code that we could reuse from the internet, etc. At around 2 a.m. we finally did it. It took us around 5 hours to develop the whole thing and it took the computer 10 milliseconds to execute it. It worked amazingly. Wendy, on the other hand spent about two and a half hours to come up with a solution which did not compare with ours in terms of overall “happiness”. You do the math: 5 hrs+5*(10 milliseconds) < 5*2.5 hrs = 12.5 hrs.
I know, I’m such a nerd. I just think its really awesome to tell the kids at the seminar that they got assigned books by a simplex. Well, I think is enough nerd-ism for a post. Cool though. See you ’round.
Filed under: Computers, algorithm, books, brainstorming, distributing, efficient, Happiness, how to find, learning, linear program, lp standards, manually, maximized, problem, simplex algorithm, systematic solution, total time
Recent Comments