My friend Brad had a really interesting real world optimization problem. He wants to have a card tournament where either 16, 28, or 40 players play. There are 4 players in each hand, and they play a number of rounds. The trick is to schedule the tournament so that each player plays all of the other players exactly once. Belive it or not, he actually had a party like this for 16 players, and he wanted to try 28 or 40. To work out evenly with *n* players, you need to have both* n/4*, and *(n-1)/3* be integers. For example, it works for the folowing combinations of players and hands played:

`(Players, hands played){4,1}
{16,5}
{28,9}
{40,13}
{52,17}
{64,21}
{76,25}
{88,29}
{100,33} `

Given that I'm the "optimization guy", I'm supposed to be able to solve problems like this. I tried soving it with mixed integer programming, but it has a really lousy LP relaxation. It turns out constraint programming is a better approach. I eventually found a web page by Warick Harvey at IC-Parc at Imperial College that gives the best known solutions for these problems. He calls it the "social golfer" problem, or "Kirkman's schoolgirl problem". (Imperial is great school, by the way. My advisor, and lots of other cool folks went to Imperial.)

I'm just posting about the problem, because it was really hard to find the page in Google, given that I wasn't searching on "Golf". If you're scheduling any tournament with more than 2 participants in each round, you're in luck.

## Comments