Contact

2 responses

1. Hi, I wonder if you’ve given any thought to Simulated Annealing as a method for finding doubles matchups. You’re trying to minimize some error, which could just be the difference in skill between the two teams, right? But for repeated matches, might also include not pairing the same people up repeatedly, or having the same person rest repeatedly. So you create a function that computes the current total score (lower is better, typically), and start by assigning everyone randomly. Then you start considering random swaps of people’s assignments, and check what the score would be after that swap. But you give a threshold, and if the swap makes the score worse by more than this threshold, you don’t do it. Then you gradually lower the threshold until it’s 0, and then after a certain number of iterations (or a certain number of iterations with no successful swaps), give up.

   The reason for the threshold, instead of just only making swaps that strictly improve the score, is that you can get stuck in a local optimum, and letting the score temporarily get worse by a little bit, it can break you out of those local optima.

   Anyways, interesting blog posts!

   Reply

   1. I’d never heard of Simulated Annealing, in fact not ‘annealing’ itself either on its own. Thanks for the enlightening comment. So I’m a bit wiser after reading the Wikipedia page. Yes I’m trying to minimise the diff. The global search is impossible. Currently the method is pretty ad-hoc. So I’ll definitely look into this method, although I still am worried a bit about the search space. My method’s ad-hoc because basically I rely on random pruning. Which is of course a very brunt tool, but well, effective. I’m at least trying to merge all the constraints into a single function and then, I’ll consider it, of course, after researching a bit more about it. Thanks for the valuable suggestion though

      Reply