Packing differently sized chunks of data into multiple bins

Question

EDIT: It seems like this problem is called "Cutting stock problem"

I need an algorithm that gives me the (space-)optimal arrangement of chunks in bins. One way would be put the bigger chunks in first. But see how that algorithm fails in this example:

Chunks        Bins
-----------------------------
AAA BBB CC DD (       ) (   )

Algorithm     Result
-----------------------------
biggest first (AAABBB ) (CC )
optimal       (AAACCDD) (BBB)

"Biggest first" can't fit in DD. Maybe it helps to build a table like this:

Size 1: ---
Size 2: CC, DD
Size 3: AAA, BBB

Size 4: CCDD
Size 5: AAACC, AAADD, BBBCC, BBBDD
Size 6: AAABBB

Size 7: AAACCDD, BBBCCDD
Size 8: AAABBBCC, AAABBBDD
Size 10: AAABBBCCDD

Answer 1

This is basically a variant of the bin-packing problem. This problem is is known to be NP-hard, so don't expect to find an efficient optimal algorithm for complex cases (i.e. with many objects and bins).

However, if your number of objects/bins is relatively small, you will probably be fine just exhaustively searching all the possible combinations with a depth-first search.

This is pretty easy to implement: just take the first object, then recursively re-run the algorithm with the first object placed in each of the bins in turn (i.e. subtracting the size of the object from the available bin space). Finally, you just need to keep track of the best "solution" found so far and return this as your final answer once you have tried all combinations.

You may also be able make this algorithm algorithm run faster by:

• Considering all objects of equal size as equivalent
• Pruning the search tree (i.e. returning early from a branch) if you can't possibly beat the current best solution e.g. when you have already found a perfect fit

Updated based on comments on problem size

Given that it looks like you have a very large number of chunks to deal with, you might want to try the following:

• Fit the largest 10-20 chunks using an exhaustive search as above
• Allocate the remainder using a largest fit approach

Answer 2

Mikera is right: this multiple Knapsack problem (a variant of the bin packing problem) is NP hard.

Here are a couple of your options (copied from my answer on a similar question):

• Brute force, or better yet, branch and bound. Doesn't scale (at all!), but will find you the optimal solution (probably not in our lifetimes though).

• Deterministic algorithm: sort the chunks on largest size and go through that list one by one and assign it the best remaining spot. That will finish very fast, but the solution can be far from optimal (or feasible). Here's a nice picture showing an example what can go wrong. But if you want to keep it simple, that's the way to go.

• Meta-heuristics, starting from the result of a deterministic algorithm. This will give you a very good result in reasonable time, better than what humans come up with. Depending on how much time you give it and the difficulty of the problem it might or might not be the optimal solution. There are a couple of libraries out there, such as Drools Planner (open source java).

Answer 3

A general best algorithm for this problem doesn't exist yet (see bin packing problem). You can find a few different approaches on wikipedia and/or googling for the "bin packing problem" and maybe "knapsack problem" would also provide some help.

Answer 4

Donald Knuth's Dancing Links algorithm is quick at finding solutions to "exact covering" problems.