Tag Archives: optimization

help Santa solve this bin packing problem

Kaggle is sponsoring a non-denominational Christmas optimization contest to help Santa solve a 3-dimensional bin packing problem [Link].

This year we’re attacking the classic bin packing problem with a twist: cram all the gifts into his sleigh, but in the order they need to be delivered! MathWorks is sponsoring the $10,000 prizes — with $4000 going to both the holder of the top spot, and also the highest-ranked team using 100% MATLAB/MathWorks as their tool. The final $2000 is the Rudolph Prize: Rudolph, won’t you lead-our-board tonight? No word yet on whether the prize pool will include an optimally-stuffed reindeer.

The problem seeks to find an optimal ordering of Christmas presents in a single 3-dimensional bin. Packages have a size in each of the three dimensions, and they can be rotated to fit into the bin. The objective is to minimize the highest placed present in the bin. The contest ends at 11:59 pm, Sunday 26 January 2014 UTC.

Santa packs a bin full of presents

is integer programming the best tool in the OR/MS toolkit?

A tweet from Marco Luebbecke contained a provocative quote from George Nemhauser’s plenary talk at the EURO-INFORMS Joint International Meeting:

This needs more discussion than 140 characters. Integer programming is truly an amazing tool for optimally solving problems that are theoretically difficult to solve. It would be hard for me to come up with reasons for why IP would not be the most important tool. What do you think?

are squirrels optimizers or satisficers?

Last month, I had the pleasure of meeting Yakov Ben-Haim and talking with him at length about info-gap decision theory. He used an example of squirrels foraging for nuts to illustrate the types of problems for which info-gap decision theory models are useful.

A squirrel needs calories to survive, and nuts provide the perfect source of calories. The squirrel has a decision to make: where should the squirrel go to forage for nuts? Different foraging locations have different potentials for nut payoffs. They also have risks (not enough food). Foraging in a new location may carry highly uncertain risks that are impossible for the squirrel to estimate (being hit by a car, eaten by a wolf, etc.)

The squirrel has two options: the squirrel can hunt in the usual area where he can obtain n nuts with certainty or he can try a new location where he has a probability P of obtaining N nuts (with N > n) and a probability (1-P) of obtaining zero nuts. Let’s say that N and P are wild guesses.

Let’s say that the squirrel is an optimizer and decides to build a decision tree to maximize the number of nuts he can collect. Using basic decision analysis, he devices that he should choose the new location if PN>n.

The squirrel's decision tree. Squirrels don't really make decision trees, do they?

If the squirrel needs to collect n nuts to survive, then maximizing is nuts (pun intended. Sorry!) Staying with the status quo guarantees survival, even if P and N are large. The payoff for the new location may be greater, but there is a 1-P chance that the squirrel would starve.  The traditional decision tree is not robust to the squirrel’s desire to survive (neither is darting in front of cars on the highway, but I digress).

On the other hand, if the squirrel needs to collect N nuts to survive, then staying with the status quo guarantees the squirrel’s demise.  The new location is worth a look no matter how risky.

In both of these scenarios, the squirrel isn’t really maximizing the subjective expected nuts that he can collect–he really wants to maximize the probability of meeting his nut threshold (the one that guarantees survival). This is a satisficing strategy (although not dissimilar from an optimizing strategy with a moving threshold). The satisficing strategy is a better bet for the squirrel than the optimization strategy in this decision context. The squirrel doesn’t always need to know the exact probabilistic information to make a good decision, as illustrated above.  In fact, he can have absolutely no idea what N and P would be to find an effective nut foraging strategy–even when there is severe uncertainty.

The idea of a squirrel building a decision tree is, of course, ludicrous. But it makes the point that what we should rethink our traditional optimization models so make sure they fit the real decision criteria on hand.  Info-gap decision theory thus focuses on satisfying a given acceptable level of what is traditionally considered the objective function value and instead optimizing robustness.  It also has philosophical implications for how one views certainty.

I’ve been looking more closely at robustness lately.  I won’t abandon my optimization models, but I will acknowledge that including robustness in certain scenarios leads to decisions that more accurately reflect the criteria at hand and decisions that could be counter-intuitive.

Yakov Ben-Haim can explain this much better than I can, so I’ll refer you to his blog about info-gap decision theory and his article about foragers in the American Naturalist if you want to learn more.

a course blog on discrete optimization

I decided to try an experiment this semester that involves possibly torturing a few grad students:  I proposed that the students in my grad-level course on discrete optimization would maintain a blog for course of the semester. Amazingly, the students in my class agreed to my little experiment!  I am happy to say that our blog, the not-so-cleverly titled Discrete Optimization Blog, has been live for two weeks now.

If you’re interested, please stop by and visit us.  Blog posts are due on Mondays at noon (from now until the first week in May).  You can read more about the blog assignment here. As far as I know, this is the first operations research course blog, and I think the students are doing a great job.

a Christmas brain teaser

When finding some math worksheets to occupy my six year old daughter on her day off of school, I discovered a Christmas brain teaser for elementary students (in pdf format):

Find a route [between twelve cities] for Santa to follow that is as short as possible. After you have found a route, compare it to others to see if they found a shorter route.

Of course, you will immediately recognize this as the TSP.  The “solution” is amusing:

Try to view this question as open-ended, or your student(s) might be working on it for days. …And if someone figures out the best answer to this question, please let me know and I’ll add it here.

Finding the optimal solution to a twelve city TSP is indeed pretty hard.  So hard, in fact, that the folks at math-drills.com couldn’t find the solution.  I have confidence that my readers can find the optimal solution in less than a day.  But please spend Christmas with your families enjoying holiday cheer.

Happy holidays!

robust Christmas shopping

I usually more or less finish my Christmas shopping before Black Friday, so I usually do not worry about optimal shopping strategies. I enjoyed reading about Aurelie Thiele’s latest paper on robust timing of markdowns.  Her blog post summarizes her new paper (she provides a link to the paper), where Aurelie and her collaborators propose a method for dynamically timing markdowns over a finite horizon using robust optimization models.

This got me thinking about how to reverse-engineer the process to get the best deals.  If you’re not willing to do Black Friday shopping (the getting up at 3am and waiting in long lines do not make up for the extra savings), then shopping for a few key items is like a stopping problem (e.g., the Secretary Problem), where a series of deals are offered (some at the same time, such as in the Sunday ads) and the consumer eventually decides to purchase exactly one item with a deadline of December 24.  When should I purchase the item?  I suppose it depends on how retailers adjust the prices from one time period to the next.

These are a few rules of thumb that I’ve learned (beware: no modeling or algorithms used here).  With a bad economy, I see no drawback to a wait and see approach, since sales continually improve and store coupons become available as shoppers stay home.  I have found that in the last three years or so, the pre-Christmas sales (not just Black Friday) are often better than the post-Christmas clearance sales.  So I stock up and do some personal shopping before the holidays.  However, the clearance sales become lucrative in February and insanely good in March (for clothes, at least).

How do you do your Christmas shopping?

Related posts:

Opt Art

Last month, Robert Bosch gave a fascinating talk on operations research and art here at Virginia Commonwealth University. His talk focused on showcasing how optimization, in particular, using entire sets of dominos to reconstruct paintings and images, such as the Mona Lisa and Marilyn Monroe. You can see his masterpieces at DominoArtwork. It was fascinating to see an illustration of how art connects to optimization.

Some links:
Bob’s OR/MS Today article
Images using knots
Science for kids article featuring Bob’s art


Get every new post delivered to your Inbox.

Join 1,877 other followers