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
7adgLbEhiCfjk
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?

5 comments:

  1. I am looking for a schedule for round robin bridge for 16 couples who play for seven months with four couples playing in different homes. Can you help me?

    ReplyDelete
    Replies
    1. Probably. Please send the specifics (couples play once a month? every couple "volunteers" to host? at any one home, does every couple play every other couple, for a total of three rounds of two simultaneous games each?) to me at rubin AT msu DOT edu.

      Delete
  2. Hi Paul, How quickly can a schedule be made for 22 tennis players of various levels. There are 11 married couples. I'd prefer for each couple to play round 1 with their spouse and then split up thereafter. I have the 11 males ranked and the 11 females ranked and ultimately have the couples ranked as well. I expect to play 6 rounds. How can I do this ?

    ReplyDelete
  3. Guess I should have included this is a round robin. My first attempt at having one of these. Thanks in advance.

    ReplyDelete
    Replies
    1. There are more details necessary, but once the details are pinned down it should be fairly easy to concoct a reasonable schedule (meaning less than an afternoon's work). If you wish, you can write to me at rubin AT msu DOT edu. It might take a round or two of emails to pin down the necessary specs.

      Delete

If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on OR-Exchange.