Bin Packing Made Easier?

I have always found the following example interesting. I remember that it was Peter Ross who first showed me this during a presentation at a conferenec we were both attending.

The example demonstrates that an algorithm can act in an unexpected way when you make a very small change to the input data.

The example is drawn from bin packing. In this problem, you are given a number of items, all of which have a weight. Let's assume that we have the following 33 items.

442, 252, 127, 106, 37, 10, 10, 252, 252, 127, 106, 37, 10, 9, 252, 252, 127, 85, 12, 10, 9, 252, 127, 106, 84, 12, 10, 252, 127, 106, 46, 12, 10

We are also given an infinite number of bins, each one having a certain capacity. Let's assume that the capacity of our bins is 524.

The aim is to pack all 33 items into as few bins as possible.

How would you do it? What algorithm would you use?

One possible algorithm is as follows:

1) Sort the items into descending order of size, thus:

442, 252, 252, 252, 252, 252, 252, 252, 127, 127, 127, 127, 127, 106, 106, 106, 106, 85, 84, 46, 37, 37, 12, 12, 12, 10, 10, 10, 10, 10, 10, 9, 9


2) Take each item in turn and place it into the first bin that will accommodate it. The bins are also considered in the order they were first used.
So, to start we have no bins available, so we open one. We take the first item (442) and place it in that bin. Now we take the next item (252). We cannot fit this into the bin we have just opened (as 442+252 > 524) so we open another bin.
The next item (252) will be placed in the second bin. The next item (252) will have to open a third bin.

... and so on.

If you apply this algorithm, you will get this solution

Bin 1: 442, 46, 12, 12, 12 = 524
Bin 2: 252, 252, 10, 10 = 524
Bin 3: 252, 252, 10, 10 = 524
Bin 4: 252, 252, 10, 10 = 524
Bin 5: 252, 127, 127, 9, 9 = 524
Bin 6: 127, 127, 127, 106, 37 = 524
Bin 7: 106, 106, 106, 85, 84, 37 = 524

You'll notice that we have a solution that requires 7 bins and, moreoever, each bin is completely full. Therefore, we know we have found an optimal solution.

As an aside, what we have just done is used a heuristic (a rule of thumb). This one is known as Largest Fit, First Fit. We could come up with many more. For example, we could sort the pieces in different ways, we could consider all the open bins before deciding which one to use etc.

The question now arises, is the largest fit, first fit heuristic always the best heuristic to use for the bin packing problem?

Let's see.

Take our list of sorted items again. That is:

442, 252, 252, 252, 252, 252, 252, 252, 127, 127, 127, 127, 127, 106, 106, 106, 106, 85, 84, 37, 37, 12, 12, 12, 10, 10, 10, 10, 10, 10, 9, 9

But this time remove an item (say 46 - which has been removed from the list above).
We know that we can use seven bins to pack these items, and have 46 units left over.

So, let's apply the largest fit, first fit heuristic and see what happens.

This is the result.

Bin 1: 442, 37, 37 = 516
Bin 2: 252, 252, 12 = 516
Bin 3: 252, 252, 12 = 516
Bin 4: 252, 252, 12 = 516
Bin 5: 252, 127, 127, 10 = 516
Bin 6: 127, 127, 127, 106, 10, 10, 10 = 517
Bin 7: 106, 106, 106, 85, 84, 10, 10, 9 = 516
Bin 8: 9 = 9

This is quite surprising (well, it is to me). We have removed an item, but had to use an extra bin.

Of course, we could develop another heuristic that only used 7 bins, but would that heuristic work well on other problem instances? Or, to put it another way, if you were presented with an instance of a problem you had not seen which heuristic would you use?

There is some work being done in an area termed hyper-heuristics (which I'll blog more about in the future) which is trying to address problems such as those described above.

If you are interested in reading more about hyper-heuristics, you might like to visit my publications page (http://www.cs.nott.ac.uk/~gxk/gxk1/publications.html).

Good introductory articles are:

1. Cowling P., Kendall G., Soubeiga E.A Hyperheuristic Approach to Scheduling a Sales Summit. In LNCS 2079, Practice and Theory of Automated Timetabling III : Third International Conference, PATAT 2000, Konstanz, Germany, August 2000, selected papers (eds Burke E.K. and Erben W), Springer-Verlag, pp 176-190, ISBN : 3-540-42421-0
2. Burke E.K., Kendall G. and Soubeiga E. (2003) A Tabu-Search Hyper-Heuristic for Timetabling and Rostering. Journal of Heuristics , 9(6), 451-470, 2003
3. Burke E., Hart E., Kendall G., Newall J., Ross P. and Schulenburg S. (2003) Hyper-Heuristics: An Emerging Direction in Modern Search Technology. Handbook of Meta-Heuristics (Glover F., ed), pp 457 – 474, Kluwer