What is the best Christmas oriented operations research issue you have seen? I'll start off with a brief blog post I made on how far Santa and his reindeer have to travel: http://mat.tepper.cmu.edu/blog/?p=494. Have you seen other papers/posts/articles?

asked 24 Dec '09, 04:05

Michael%20Trick's gravatar image

Michael Trick ♦♦
accept rate: 20%

edited 11 Dec '12, 14:31

fbahr's gravatar image

fbahr ♦


I'll add another one. What algorithm does a string of lights 50 feet long use to get a knot right in its middle?

(24 Dec '09, 22:10) Michael Trick ♦♦

Another possibility: The Secret Santa's Problem solved via constraint programming by Hakan Kjellerstrand http://www.hakank.org/constraint_programming_blog/2009/12/merry_christmas_secret_santas.html

(25 Dec '09, 13:25) Michael Trick ♦♦

Kaggle has an optimization problem, rather than a predictive modelling problem, competition at the moment. The Traveling Santa Problem.

Essentially you are given a list of 150,000 (x,y) coordinates, and you need to find two paths through all of them (note not routes, so you don't need to return to starting point). The trick is that none of the edges can be shared between the two paths. The objective function value is the longer of the two paths.


answered 20 Dec '12, 03:41

DC%20Woods's gravatar image

DC Woods ♦
accept rate: 5%

Here is a variant of the Secret Santa problem: http://www.hakank.org/constraint_programming_blog/2009/12/1_year_anniversary_and_secret_1.html. The objective is to maximize the "Secret Santa distance", i.e. to previous Secret Santa assignments.


answered 29 Dec '09, 19:23

Hakan%20Kjellerstrand's gravatar image

Hakan Kjelle...
accept rate: 0%

Straight from the "news":

The Traveling (Christmas Tree) Salesman Problem

[published in INFORMS' Analytics magazine]

PS, for German readers only: Optimiert Weihnachten [Amazon], the book.

[Or, via Springer - for "just" 269.25€ ...so it must be excellent, I'd guess.]


answered 11 Dec '12, 12:45

fbahr's gravatar image

fbahr ♦
accept rate: 13%

edited 12 Dec '12, 04:15

Optimiert Weihnachten! Das ist ja der Knaller!! :-D [sorry, non-German readers]

(12 Dec '12, 03:43) Marco Luebbecke ♦

With all those Christmas cards being sent to people all at the same time, I guess somebody at USPS is going crazy.

Sounds like multiple instances of the TSP problem with capacity constraints.


answered 25 Dec '09, 07:09

Mark's gravatar image

Mark ♦
accept rate: 9%

"multiple instances of the TSP problem with capacity constraints": In other words: "the Vehicle Routing Problem" :P

(25 Dec '12, 11:23) Florents Tselai

I suppose there is a knapsack problem in there with Santa's toy bag and all of those gifts.


answered 26 Dec '09, 23:19

larrydag's gravatar image

accept rate: 0%


A knapsack model would imply that you only get what Santa could fit, which leaves a lot of ponies unexplained. I think it's more of a packing problem -- in what order do you load the bag so that (a) the next present to be delivered is near the top (trivial if you know the route) and (b) the ponies don't crush any of the fragile stuff (NP hard, where NP = Number of Ponies).

(28 Dec '09, 19:49) Paul Rubin ♦♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 24 Dec '09, 04:05

Seen: 4,918 times

Last updated: 25 Dec '12, 11:23

OR-Exchange! Your site for questions, answers, and announcements about operations research.