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.
| Date | Game 1 | Game 2 | Game 3 |
|---|---|---|---|
| 1 | abcD | efgH | iJkl |
| 2 | aeFj | Bdhl | cgIk |
| 3 | agHj | Bfkl | cdeI |
| 4 | Abek | Cghl | dFij |
| 5 | ahiK | bcfG | dejL |
| 6 | acEl | bGij | dfhK |
| 7 | adgL | bEhi | Cfjk |
| 8 | Afil | bchJ | Degk |
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?
