gorithm

I'm a very streaky poster

I haven't posted in ages, and I sort of build up a backlog.  So tonight you get three real posts (plus this fine one).  That's not a very good way to do things, I know. 

On the unlikely chance you actually know me, you might be interested to know that we all moved to a new house!  I'm sitting among the boxes as we speak. That could be why I haven't posted recently :-)

Scheduling a card tournament with 4 players

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. 

George Dantzig, inventor of the simplex algorithm, dies at 90

George Dantzig died this week at 90.  He was the inventor of the simplex algorithm, which made it possible to solve linear programming problems.  The Operations Research society, INFORMS, has an obituary. To a large extent, he made my field of OR possible, since it was the first time real interesting problems could be solved with a computer.  This may seem odd to non-techies, but I use the simplex algorithm every day to solve problems.  He was a giant in our field.

I hope that when I die, I rate a Slashdot posting.
He even has his own urban legend.

We need $4 gas!

Here's an interesting interview with Tom Friedman, suggesting we should tax gas to be $4 a gallon.  His argument is that neocons and greens both have a vested interest in driving energy independence.  My English wife says that all the time.  Gas is the equivalent of $8/gallon now in Great Britian (given the exchange rate), and you do notice a lack of Hummers driving around.