5
1

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 ♦♦
4.1k41533
accept rate: 20%

edited 11 Dec '12, 14:31

fbahr's gravatar image

fbahr ♦
4.6k716

2

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 ♦♦
4

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.

link

answered 20 Dec '12, 03:41

DC%20Woods's gravatar image

DC Woods ♦
4.1k22546
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.

link

answered 29 Dec '09, 19:23

Hakan%20Kjellerstrand's gravatar image

Hakan Kjelle...
491127
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.]

link

answered 11 Dec '12, 12:45

fbahr's gravatar image

fbahr ♦
4.6k716
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.

link

answered 25 Dec '09, 07:09

Mark's gravatar image

Mark ♦
3.6k22350
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.

link

answered 26 Dec '09, 23:19

larrydag's gravatar image

larrydag
511
accept rate: 0%

1

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

By RSS:

Answers

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

Tags:

×53
×29
×1

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.