## Saturday, April 30, 2011

### An Unbalanced Round Robin Bridge Schedule

Ages ago, while studying (sort of) for my doctorate in mathematics, I played a significant amount of duplicate bridge, frequently with my grad school buddies Bluto and Dawn and my now-long-lost love (She Who Will Not Be Named).  Bluto and Dawn (who are married) are now retired, and not too long ago I got an e-mail from Bluto.  He and Dawn continue to play bridge with a group of friends, and they have a sort of league set up.  Since he and Dawn both studied math, the duty of constructing a schedule for the league naturally fell to them.

The way their league functions is as follows.  Once a month, couples get together at various houses, with four couples at each house (that being the most people couples are willing to host). Their league has 12 couples, so there are three venues operating simultaneously.  At each house, each of the four couples plays against each of the other couples (so three games per venue per date).  The objectives in forming the schedule are to minimize the variation in how often any pair of couples faces each other, and simultaneously to minimize the variation in how often a couple is called upon to host a game.  The planning horizon is eight dates.

Dawn (the brighter of the two) was apparently able to construct a balanced schedule for 16 couples, four venues per date and an unspecified horizon (which I'm sure was divisible by five), despite being hampered by a degree in abstract algebra.  Neither of them could find a schedule for 12 couples/eight dates, in part because it cannot be balanced: each couple plays three games per date, so 24 games total, which means they cannot play the other 11 couples an equal number of times.  Bluto asked me if this was an operations research problem, which it most definitely is.

It can be attacked in a variety of ways (mixed integer program, constraint program, metaheuristic); I chose to try a MIP model first, since that's the type of software with which I'm most familiar.  As with many MIP problems, the model was easy but the solution was a bit time-consuming, even after tweaking the model to eliminate some of the symmetry that plagues the problem.

I won't bore anyone with the model details, but I thought I'd post the best schedule I found, in case anyone else happens to be trying to schedule 12 team round-robins (although I suspect the parameters of this particular problem are rather unusual).  In the tables below, couples are identified with the letters 'a' through 'l'; hosts are capitalized.

DateGame 1Game 2Game 3
1abcDefgHiJkl
2aeFjBdhlcgIk
3agHjBfklcdeI
4AbekCghldFij
5ahiKbcfGdejL
6acElbGijdfhK
8AfilbchJDegk

Charitably assuming I transcribed that correctly, each team plays every other team either two or three times. (With 12 teams playing three games on each of eight dates, for 24 games total per team, you would expect to play nine of the other 11 teams twice and the other two three times each, so this tracks.)  Everyone hosts exactly twice.  In terms of meeting Bluto's stated criteria, it does pretty well; but looking at it, I wonder if I should have added a penalty for couples hosting on consecutive dates, or tried to maximize the minimum elapsed time between hosting assignments for any couple?