How Should Santa Pair Up His Reindeer?

It’s almost Christmas time and Santa is probably very busy with some last-minute preparations before his longer-than-7.5-million-kilometer trip around the world. One of the many things he has to worry about is how to pair up his reindeer in front of the sleigh. We all know that Rudolf goes right in front of everyone else because of his shiny nose, but what about his other eight four-legged friends? The traditional Christmas carols tell us that the reindeer are typically arranged in four pairs, front to back, as follows:

Dasher, Dancer

Prancer, Vixen

Comet, Cupid

Donner, Blitzen

Therefore, we are going to assume that this is an arrangement that works pretty well (after all it’s been working since 1823). As someone with a degree in a STEM field (he wouldn’t reveal which, though), Santa can’t stop thinking about this interesting question: “Are there other good ways to pair up my reindeer?” Before we can answer that question, we need to define what a “good” pairing of reindeer is. After working tirelessly on Christmas eve, Santa’s reindeer have all the other 364 days of the year to hang out and get to know each other. As in every group of friends who spend a lot of time together, some friendships become closer than others. So it’s reasonable to expect that Rudolf’s eight friends will have a favorite companion for side-by-side galloping, a second favorite, a third favorite, etc. In addition, there’s one more important detail when it comes to reindeer pairings, according to Mrs. Claus: some of them like to be on the left side (Dasher, Prancer, Comet, and Donner), while others prefer to ride on the right side in front of Santa’s sleigh (Dancer, Vixen, Cupid, and Blitzen). Before you mention that I should also consider that male reindeer would rather be side-by-side with female reindeer, there’s scientific evidence that all of Santa’s reindeer are female, so we don’t have to worry about that.

After a nice conversation in front of his cozy fireplace, Santa was kind enough to provide me with the following lists of pairing preferences for each of his reindeer; though he vehemently asked me not to show any of this to his furry friends. I’m counting on you, my readers, to keep these lists to yourselves! The names in each list are sorted in decreasing order of pairing preference. The lefties appear in blue, while the righties appear in red (any resemblance to US political parties is a mere coincidence):

Dasher: Dancer, Cupid, Vixen, Blitzen

Prancer: Vixen, Blitzen, Dancer, Cupid

Comet: Cupid, Dancer, Blitzen, Vixen

Donner: Blitzen, Vixen, Dancer, Cupid

Dancer: Prancer, Comet, Dasher, Donner

Vixen: Dasher, Donner, Prancer, Comet

Cupid: Prancer, Dasher, Comet, Donner

Blitzen: Comet, Prancer, Donner, Dasher

Note that if we were to adhere to the lefties’ first picks, we’d end up with the traditional line-up. We are now ready to define what a good pairing is: a pairing is good (a.k.a. stable) if no one has an incentive to change pairs. In other words, if A is paired up with B, and A prefers C to B, it so happens that C, who is paired up with D, prefers D to A. (Note: this problem is known in the literature as the stable marriage problem and it arises in real life, for example, in the context of the National Resident Matching Program, which pairs up medical residents with hospitals every year in the United States.) Obviously, the traditional pairing shown above satisfies these goodness/stability conditions, given the reindeer’s preferences.

What Santa would like to know is whether or not there are other good pairings in addition to the traditional one. If so, he can add some variety to his line-up and the reindeer won’t get so bored by galloping side-by-side with the same companion every year. How can we help Santa answer this question? Using Operations Research, of course! More precisely, Constraint Programming (CP).

Constraint Programming is a modeling and solution paradigm for feasibility and optimization problems that allows one to represent complicated requirements (such as the stability condition above) in ways that are often easier and simpler than using traditional O.R. techniques such as Integer Programming. For example, indexing variables with variables and expressing logical constraints such as implications are a piece of cake in CP. Here’s a CP model written in the Comet language (not to be confused with Comet the reindeer) that answers Santa’s question. It essentially enforces the stability condition for every choice of A, B, C, and D.

The good news is that, in 3 milliseconds, that CP model finds all of the five different stable pairings. Here they are:

Update (1/1/2012): Here’s an AIMMS version of the CP model, kindly created and provided by Chris Kuip. Look for this reindeer example, including an accompanying graphical user interface, in an upcoming update to the set of examples in AIMMS.

I hope Santa reads this blog post before Christmas eve, but in case he doesn’t, please tell him to check this out if you run into him this holiday season. I’m sure his reindeer would appreciate a little change after 189 years.

11 Comments

Filed under Applications, Constraint Programming, Holidays, Modeling, Traveling Salesman Problem

11 responses to “How Should Santa Pair Up His Reindeer?

  1. I’m willing to believe that Vixen is female. Not sure about Prancer: maybe female, maybe just cross-dressing. But what kind of reindeer parents would name daughters Donner (Thunder) and Blitzen (Lightning)??

  2. orbythebeach

    Paul: To me, Donner and Blitzen are as good a girl’s name as are other usual American choices such as Morgan and Taylor. I have a hard time accepting these as girl’s names. I can’t explain why; it just sounds strange. Maybe because the first Morgan and Taylor I ever met were men.

  3. I know what you mean. It took me a while to adjust to names like that. (It helped that Morgan Fairchild — not her real name, by the way — was hot. Probably still is.) I don’t think naming a girl Morgan or Taylor is likely to induce the sort of gender anxiety that naming her Thunder would. :-)

  4. Pingback: Mathblogging.org Weekly Picks « Mathblogging.org — the Blog

  5. Pingback: Promote O.R. by Taking Folks by Surprise | O.R. by the Beach

  6. I don’t suppose anyone has pointed out that the name of ‘Donner’ in the graphic is misspelled as ‘Donder’?

  7. orbythebeach

    I had noticed that, but thought it was a valid, alternative spelling. From your comment, it seems I was wrong.

  8. Actually, I think Donder is the Dutch word for thunder (Donner in German). Hard to know whether Santa’s reindeer are German or Dutch. I suppose we’d have to try to find out what kinds of beer they like.

  9. orbythebeach

    Ah! So maybe Donder is not a typo after all…

  10. emily

    I always thought Dasher,Donner,Comet and Blitzen were boys and the rest girls

  11. prubin73

    Vixen sounds female. If Cupid is female, Roman mythology is about to get a rewrite.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s