Forever Learning

Forever learning and helping machines do the same.

Bin Packing Too Many Features

with 2 comments

Packed MotorbikeMy girlfriend has been struggling with an interesting little problem lately. She was asked to determine the optimal distribution of medicine boxes and bottles over a set of adaptable cabinets; under volume as well as weight constraints. Not an easy task for a computer scientist; much less for a hospital pharmacist in training.

After describing the problem to me last night I (unhelpfully) mumbled that “this sounds like a variable sized bin packing problem to me, you can’t solve the kind of thing in Excel, you probably need an LP solver”.

Apparently I was wrong. It already seemed obvious to me that Excel suffers from a severe case of feature bloat, but this is just absurd.

Advertisements

Written by Lukas Vermeer

September 19, 2012 at 17:19

Posted in Code, Mathematics

Tagged with , ,

2 Responses

Subscribe to comments with RSS.

  1. There are complete courses being taught around the excel solver plugin, which has been in excel for years. (For example the logistics course in the MBI master at UU)

    However, solving bin packing needs an ILP solver (LP can be done in polynomial time and Bin Packing is NP-hard) and the Excel solver sucks at that.

    If you can somehow reduce it to knapsack, you could use the dynamic programming recursion in Excel, allowing you to solve the problem with just addition, the MAX function and simple cell references.

    Paul Bouman

    September 19, 2012 at 18:46

    • Somehow I suspected you were going to have to correct me on something on this one, Paul, but I’m glad you did. The difference between LP and ILP had completely escaped my memory. Thanks for the refresher course!

      Looks like we’ll need a proper solver after all; and possibly a couple of consultants who specialise in this kind of thing. I’m way out of my comfort zone here. 🙂

      Lukas Vermeer

      September 19, 2012 at 19:14


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

%d bloggers like this: