Feature Column from the AMS

Bin Packing

3. More approaches to bin packing

In the procedures examined so far for attempting to find the smallest number of bins into which to pack a collection of weights, we have imagined that the items to be packed are given in a list, and we have used this list to "drive" the packing as we considered different procedures for filling bins. One can, in fact, think of this list as being generated dynamically, and one does not know the item that will be generated next in advance. An item arrives to be packed, then another item, and then another. All of the algorithms we have discussed so far have the property that the fact that there may be more items in the list to pack (farther to the right than one being currently worked on) does not affect what is done to pack the current item. Such algorithms are known as on-line. The idea for on-line algorithms, whether they are being used to solve bin packing problems or other combinatorial optimization problems, is that not all the components of the problem are known in advance. In the bin packing case one can imagine an industrial situation where items with different weights are being produced and then are being placed in bins which are at some stage to be shipped to customers.

In contrast to an on-line point of view is the possibility of using an off-line approach. When thinking of the bin packing problem from an off-line point of view, one thinks of having all of the items to be packed in advance. Thus, one can consider other types of approaches to packing the items. In particular, one can ask for the given weights to be packed if there is some rearrangement of the weights into a list different from the original which might be used to give a better result for the number of bins required. If there are n items to pack, the number of potential lists for these n items is n!, since the first item can be chosen in n ways, the second in n-1, etc., giving n! as the number of different possible lists. Intuitively, since given a packing we typically find a list which would have given rise to this packing for a particular packing algorithm, we see that choosing a list for an optimal packing has the flavor of looking for a needle in a haystack. (Even for 20 items to pack, say, 20! is a very large number.)

In the on-line environment using FF, for example, at a given stage one may have so many open bins that it becomes economically unrealistic to have so many empty bins being monitored in the hope that later items will fit efficiently into them. This suggests a version of bin packing where one seeks a packing heuristic but is limited to having at most K bins open at a given time. These heuristics are known as bounded-space on-line heuristics. For the heuristics discussed above one can try to develop a K open bin bounded space version of the heuristic. However, the situation for K > 1 open bins raises some tantalizing issues. Not only do we have the option of specifying the way the bins are packed, we have an option of specifying when a bin will be shut down (closed permanently) other than when it is completely full! Suppose that we have K open bins and we now must pack a weight which does not fit into any of the open bins. Since we must open a new bin, we have to choose an old bin to shut down. This can be done either by picking the lowest numbered bin to shut down (this is in the spirit of FF) or by shutting down the bin which is closest to being completely full (this is in the spirit of BF). Using either the FF or BF packing rule with the FF or BF closing rule, we get four(!) new heuristics in the K open bin environment.

In Example 1 we noticed that the very large item to pack at the end of the list made it necessary to have an extra bin opened at the end. Intuitively, it seems like a good idea to try to pack large items first. This is the same strategy you would use to pack a suitcase for a vacation; you would not leave a large-volumed item to the end! This suggests the following approach to off-line bin packing. Choose the list where the weights appeared in sorted order, from largest to smallest. Now use any of the algorithms that we have discussed to carry out the packing.

We have already discussed four packing algorithms: NF, FF, BF, and WF and we now have four new approaches which we will call NFD, FFD, BFD, and WFD where in each case the "D" refers to decreasing. For example, FFD means First Fit Decreasing, and would give rise to the packing for the weights in Example 1 shown below. Note that this packing is optimal.

Example 1's weights optimally packed in 4 bins using FFD

Not only can one not pack these weights into fewer bins but also there is no wasted space. Of course, there are many situations where optimal packings still have unused space. Among all packings of this kind one might look for that packing with various characteristics, say, that the fewest bins have extra space. Alternatively, one might want a packing where the number of bins used is minimal but as many bins as possible have some extra room. (A little extra space might allow putting packing material into the bin to prevent breakage during shipment.) Note also that once one has an optimal packing, one can often either rearrange the items in one of the bins or between bins in a way that achieves some secondary goal beyond minimizing the number of bins.

The fact that FFD yielded an optimal solution in Example 1 does not mean that this will be the case for other problems the method is applied to. Perhaps you are not surprised to learn that First Fit Decreasing does not always yield optimal solutions. Here is an example:

Example 2:

Suppose that one has bins of capacity 20. What would be the fewest bins needed to pack weights of size 4, 8, 7, 10, 3, 8? Since the sum of the weights is 40, with bins of capacity 20 a packing with only 2 bins might be achieved. In fact there is indeed a packing needing only two bins: Bin 1: 8, 8, 4 and Bin 2: 10, 7, 3. In this notation the item of weight 8 is at the bottom of Bin 1, next comes the item of weight 8, and the item of size 4 occupies the space at the top of the bin. Note that this solution is not unique because the items within the bin can be permuted. However, with this particular list none of the procedures, NF, FF, BF, WF, NFD, FFD, BFD, or WFD yields an optimal number of bins. In each case 3 bins are required, as you can check for yourself. If one had been given, say, the list 8, 4, 8, 10, 7, 3 then NF, FF, BF, and WF would all give rise to an optimal packing (with the weights packed slightly differently from the solution given above).

After finding eight appealing heuristics or approximation algorithms in the search to find an optimal solution to the bin packing problem, one might be tempted to wonder if finding an optimal solution to bin packing is very hard! Mathematicians have attempted to show that some problems are indeed very hard using a variety of approaches. One of these approaches involves showing that a problem is NP-complete. Intuitively, a problem Z is NP-complete when it has been shown that if this problem can be solved in polynomial time, then so can a very large number of other problems; while if Z can be proved to require an exponential amount of time to solve, then so will all of the other problems. Thus, the NP-complete problems are thought to be hard to solve but either all of the problems are, in fact, not really that hard (in the sense of only requiring polynomial work) or all of the problems actually require an exponential amount of work to solve. Since many NP-complete problems are of great importance for applications in operations research (management science), the fact that mathematicians and computer scientists are unsure of the status of the NP-complete problems is frustrating! You guessed it--the "decision version" of bin packing is known to be NP-complete. That is, given a capacity C and a list L of weights and an integer D the problem of determining if the weights in L can be packed into D or fewer bins of capacity C is NP-complete. Thus, finding approximately optimal solutions for bin packing in polynomial time is probably the best we can hope for.