Bin packing

Introduction

The bin packing problem is a classic problem with a long history. It’s one of the earliest problems shown to be intractable. The problem lends itself to simple algorithms that need clever analysis.
This post contains a number of classic approximate bin packing algorithms, showing their implementation in C and examples of the results they produce.

The problem is to find the minimum number k of identical bins of capacity C needed to store a finite collection of weights w1, w2, w3, … , wn so that no bin has weights stored in it whose sum exceeds the bin’s capacity. Traditionally, C is 1, and the weights wn are real numbers, but for this article I’m going to use a positive integer C, and the weights are positive integers less than C.

An important consideration in bin packing is whether we need to pack the items in a fixed order (in a real world application, the order in which they arrive), or if we are able to rearrange them in the hope of achieving a better packing. Algorithms for solving the first case are called online algorithms, while those for the second are offline algorithms. Offline algorithms will require additional storage for holding the rearranged items.

The rest of this post is a collection of online and offline algorithms for solving the bin packing problem. Each algorithm is in the form of a function with a prototype like this:

unsigned int fit(unsigned int binsize, unsigned int *sizes, unsigned int *bins,
        unsigned int numitems)

The arguments are as follows:
binsize: This is C, the capacity of the bins.
sizes: These are the weights of the individual items, as a sequence of integers.
bins: This is an array of the same size as sizes that the caller passes in. The packing function will populate it with the 0-based bin number of the bin that has been used to store the corresponding item in the sizes array. Algorithms may rearrange the items in the sizes array, but they ensure that the bin numbers in the bins array still correspond.
numitems: The size of the sizes and bins arrays.

The return value is the number of bins used.

For the examples, C, the capacity of the bins, is 7, and we want to pack items with the following weights: 1, 4, 9, 4, 1, 5, 8, 3, 2, 5, 7, 3, 2, 6.

A typical test program will look like this:

#include <stdio.h>

#include <binpack.h>

int main(void)
{
    unsigned int sizes[] = {1, 4, 9, 4, 1, 5, 8, 3, 2, 5, 7, 3, 2, 6};
    const unsigned int numitems = 10;
    unsigned int bins[numitems];
    const unsigned int binsize = 7;
    unsigned int item;
    unsigned int bins_used = fit(binsize, sizes, bins, numitems);
    printf("%d bins were used\n", bins_used);
    for (item = 0; item < numitems; item++) {
        printf("Item #%d (size %d) is in bin %d\n", item, sizes[item], bins[item]);
    }
    return 0;
}

Next Fit (NF)

Our first bin-packing algorithm is very simple:

  1. Place each item in a single bin until an item will not fit
  2. When an item won’t fit, close that bin and begin another

You can imagine this as being for a real world situation where the bins are shipped off as soon as they cannot take the next item. Since only one bin is in use at once, this requires minimal space for the packing operation.

The Next Fit algorithm can’t use more than 2 × M, the optimal number of bins, since for any two adjacent bins, their combined weights can’t be less than 1, as in that case the contents of the second bin would have been placed in the first. Consequently the combined weight of all of the bins can’t be less than half the total weight, so no more than 2M bins are required.

unsigned int next_fit(unsigned int binsize, unsigned int *sizes, unsigned int *bins,
        unsigned int numitems)
{
    unsigned int bin = 0;
    unsigned int capacity = binsize;
    unsigned int item;
    for (item = 0; item < numitems; item++) {
        if (sizes[item] > capacity) {
            /* Start a new bin */
            bin++;
            capacity = binsize;
        }
        /* Put item in bin */
        capacity -= sizes[item];
        bins[item] = bin;
    }
    return bin + 1;
}

Here are the results of the Next Fit algorithm:

7 bins were used
Item #0 (size 1) is in bin 0
Item #1 (size 4) is in bin 0
Item #2 (size 9) is in bin 1
Item #3 (size 4) is in bin 2
Item #4 (size 1) is in bin 2
Item #5 (size 5) is in bin 2
Item #6 (size 8) is in bin 3
Item #7 (size 3) is in bin 4
Item #8 (size 2) is in bin 4
Item #9 (size 5) is in bin 4
Item #10 (size 7) is in bin 5
Item #11 (size 3) is in bin 5
Item #12 (size 2) is in bin 6
Item #13 (size 6) is in bin 6

Bin packing by Next Fit (NF) algorithm

Figure 1: Bin packing by Next Fit (NF) algorithm

First Fit (FF)

Looking at the results of Next Fit, it’s clear that we could better fill the bins, and possibly even use fewer bins, if we could keep a bin open when it won’t accommodate the next item, in the hope that a smaller item might come along in future that will fit. This is the basis of First Fit, which is a greedy approximation algorithm:

  1. Try to place the item in the first bin that will accommodate it
  2. If no bin is found, start a new bin

You can easily see that First Fit never uses more than 2 × M, the optimal number of bins, since more than 1 bin can be half full, or otherwise the contents of two half-full bins could be combined. In fact, it has been proved that First Fit never uses more than 1.7M bins.
If we store the bins in a balanced binary search tree like an AVL tree the algorithm can be implemented in O(n log n) time.

First, we need an algorithm to find the first element greater than or equal to a value in an AVL tree:

void *avltree_first_fit(const avltree *tree, const void *data)
{
	void *found = NULL;

	avltreenode *node = tree->root;
	while (!found && node != NULL) {
		int rv = tree->compare(node->data, data);
		if (rv >= 0) {
			found = node->data;
		}
		else {
            node = node->right;
		}
	}
	return found;
}

Then we can use that to find the bin to use in the First Fit algorithm:

bin *find_first_bin(const avltree *tree, unsigned int size)
{
    bin b = {0, size};
    return avltree_first_fit(tree, &b);
}

unsigned int first_fit(unsigned int binsize, unsigned int *sizes, unsigned int *bins,
        unsigned int numitems)
{
    unsigned int bins_used = 0;
    unsigned int item;
    avltree *tree = avltree_create((avltree_cmpfn)bin_compare);
    if (tree == NULL) {
        return 0;
    }
    for (item = 0; item < numitems; item++) {
        bin *b = find_first_bin(tree, sizes[item]);
        if (b) {
            /* Add to this bin */
            avltree_remove(tree, b);
            bins[item] = b->id;
            bin_use(b, sizes[item]);
            avltree_add(tree, b);
        }
        else {
            /* Create a new bin and add to it */
            b = bin_create(bins_used, binsize);
            bins[item] = bins_used;
            bin_use(b, sizes[item]);
            avltree_add(tree, b);
            bins_used++;
        }
    }
    avltree_for_each(tree, (avltree_forfn)bin_delete);
    avltree_delete(tree);
    return bins_used;
}

These are the results with First Fit. Notice how the bins are no longer being filled in sequence.

7 bins were used
Item #0 (size 1) is in bin 0
Item #1 (size 4) is in bin 0
Item #2 (size 9) is in bin 1
Item #3 (size 4) is in bin 0
Item #4 (size 1) is in bin 0
Item #5 (size 5) is in bin 2
Item #6 (size 8) is in bin 3
Item #7 (size 3) is in bin 2
Item #8 (size 2) is in bin 2
Item #9 (size 5) is in bin 4
Item #10 (size 7) is in bin 5
Item #11 (size 3) is in bin 4
Item #12 (size 2) is in bin 3
Item #13 (size 6) is in bin 6

Bin packing by First Fit (FF) algorithm

Figure 2: Bin packing by First Fit (FF) algorithm

Best Fit (BF)

The idea of Best Fit is to try to pack each item in the tightest spot available, in the hope that this will better fill the bins:

  1. Try to place the item in the fullest bin that will accommodate it, i.e., the bin that will leave the least room left over
  2. If no bin is found, start a new bin

This has been proved to use no more than 1.7 × M bins, the same upper bound as First Fit.
It can also be implemented in O(n log n) time with an AVL tree to store the bins.

Here is the function to find the least element greater than or equal to a value in an AVL tree:

void *avltree_best_fit(const avltree *tree, const void *data)
{
    void *best = NULL;
    unsigned int found = 0;
    avltreenode *node = tree->root;
    while (node != NULL && !found) {
        int result = tree->compare(node->data, data);
        if (result > 0) {
            if (best == NULL || tree->compare(node->data, best) < 0) {
                best = node->data;
            }
            node = node->left;
        }
        else if (result < 0) {
            node = node->right;
        }
        else {
            best = node->data;
            found = 1;
        }
    }
    return best;
}

We can now use this to find the bin to use in the Best Fit algorithm:

bin *find_best_bin(const avltree *tree, unsigned int size)
{
    bin b = {0, size};
    return avltree_best_fit(tree, &b);
}

unsigned int best_fit(unsigned int binsize, unsigned int *sizes, unsigned int *bins,
        unsigned int numitems)
{
    unsigned int bins_used = 0;
    unsigned int item;
    avltree *tree = avltree_create((avltree_cmpfn)bin_compare);
    if (tree == NULL) {
        return 0;
    }
    for (item = 0; item < numitems; item++) {
        bin *b = find_best_bin(tree, sizes[item]);
        if (b) {
            /* Add to this bin */
            avltree_remove(tree, b);
            bins[item] = b->id;
            bin_use(b, sizes[item]);
            avltree_add(tree, b);
        }
        else {
            /* Create a new bin and add to it */
            b = bin_create(bins_used, binsize);
            bins[item] = b->id;
            bin_use(b, sizes[item]);
            avltree_add(tree, b);
            bins_used++;
        }
    }
    avltree_for_each(tree, (avltree_forfn)bin_delete);
    avltree_delete(tree);
    return bins_used;
}

These are the results of the Best Fit algorithm. Comparing them to First Fit, notice how item #11 was placed in bin 5, rather than bin 4, because bin 5 had the lesser amount of free space while still being able to accommodate it.

7 bins were used
Item #0 (size 1) is in bin 0
Item #1 (size 4) is in bin 0
Item #2 (size 9) is in bin 1
Item #3 (size 4) is in bin 0
Item #4 (size 1) is in bin 0
Item #5 (size 5) is in bin 2
Item #6 (size 8) is in bin 3
Item #7 (size 3) is in bin 2
Item #8 (size 2) is in bin 2
Item #9 (size 5) is in bin 4
Item #10 (size 7) is in bin 5
Item #11 (size 3) is in bin 5
Item #12 (size 2) is in bin 3
Item #13 (size 6) is in bin 6

Bin packing by Best Fit (BF) algorithm

Figure 3: Bin packing by Best Fit (BF) algorithm

Worst Fit (WF)

This is the dual of Best Fit, in which each item is placed in the largest space available.

  1. Try to place the item in the least full bin that will accommodate it, i.e., bin that will leave the most room left over
  2. If no bin is found, start a new bin

Although this is the dual of Best Fit, the data structure to use is a heap, rather than a binary search tree, because we want the bin with the most space.

unsigned int worst_fit(unsigned int binsize, unsigned int *sizes, unsigned int *bins,
        unsigned int numitems)
{
    unsigned int bins_used = 0;
    unsigned int item;
    maxheap *heap = maxheap_create();
    if (heap == NULL) {
        return 0;
    }
    for (item = 0; item < numitems; item++) {
        bin *b = maxheap_remove_max(heap);
        if (b && b->capacity < sizes[item]) {
            /* Too small; put b back */
            maxheap_add(heap, b, b->capacity);
            b = NULL;
        }
        if (!b) {
            /* Create a new bin */
            b = bin_create(bins_used, binsize);
            bins_used++;
        }
        bins[item] = b->id;
        bin_use(b, sizes[item]);
        maxheap_add(heap, b, b->capacity);
    }
    maxheap_for_each(heap, (maxheap_forfn)bin_delete);
    maxheap_delete(heap);
    return bins_used;
}

These are the results for Worst Fit. Notice when comparing to Best Fit that item #12 was placed in bin 5 rather than bin 3, because bin 5 had more space.

7 bins were used
Item #0 (size 1) is in bin 0
Item #1 (size 4) is in bin 0
Item #2 (size 9) is in bin 1
Item #3 (size 4) is in bin 0
Item #4 (size 1) is in bin 0
Item #5 (size 5) is in bin 2
Item #6 (size 8) is in bin 3
Item #7 (size 3) is in bin 2
Item #8 (size 2) is in bin 2
Item #9 (size 5) is in bin 4
Item #10 (size 7) is in bin 5
Item #11 (size 3) is in bin 4
Item #12 (size 2) is in bin 5
Item #13 (size 6) is in bin 6

Bin packing by Worst Fit (WF) algorithm

Figure 4: Bin packing by Worst Fit (WF) algorithm

First Fit Decreasing (FFD)

A recurring theme with the algorithms we’ve seen is that they are very susceptible to the order of the items. In particular, if large items follow small ones it’s hard to accommodate them in the open bins and a new one often needs to be opened for them.

It’s this insight that drives the next algorithms, which operate by first sorting the items in descending order of size, so the largest items come first, with the intention that the smaller items will then fit into the gaps they leave. Note that this requires that we can collect all of the items together before we start packing, in other words, these are offline algorithms as described in the introduction.

The first such algorithm is a First Fit after sorting the items:

  1. Sort the items to be inserted in decreasing order by size
  2. Go through the items in sorted order
    1. Try to place the item in the first bin that will accommodate it
    2. If no bin is found, start a new bin

It can been proved that First Fit Decreasing uses at most (4M + 1) / 3 bins if the optimal is M.

For this algorithm we need a couple of utilities to compare and sort unsigned integers:

int compare_uints_decreasing(const void *v1, const void *v2)
{
    const unsigned int *p1 = v1;
    const unsigned int *p2 = v2;
    if (*p1 > *p2) {
        return -1;
    }
    if (*p1 < *p2) {
        return 1;
    }
    return 0;
}

void sort_uints_decreasing(unsigned int *sizes, unsigned int numitems)
{
    qsort(sizes, numitems, sizeof(unsigned int), compare_uints_decreasing);
}

With those in place, we just need to sort the items and then perform the existing First Fit on them:

unsigned int first_fit_decreasing(unsigned int binsize, unsigned int *sizes, unsigned int *bins,
        unsigned int numitems)
{
    sort_uints_decreasing(sizes, numitems);
    return first_fit(binsize, sizes, bins, numitems);
}

These are the results. Notice that this time we have an optimal packing, with only 6 bins used. In fact I got an optimal packing like this for all of the offline algorithms.

6 bins were used
Item #0 (size 9) is in bin 0
Item #1 (size 8) is in bin 1
Item #2 (size 7) is in bin 2
Item #3 (size 6) is in bin 3
Item #4 (size 5) is in bin 4
Item #5 (size 5) is in bin 4
Item #6 (size 4) is in bin 3
Item #7 (size 4) is in bin 5
Item #8 (size 3) is in bin 2
Item #9 (size 3) is in bin 5
Item #10 (size 2) is in bin 1
Item #11 (size 2) is in bin 5
Item #12 (size 1) is in bin 0
Item #13 (size 1) is in bin 5

Bin packing by First Fit Decreasing (FFD) algorithm

Figure 5: Bin packing by First Fit Decreasing (FFD) algorithm

Best Fit Decreasing (BFD)

This is a Best Fit after sorting the items.

  1. Sort the items to be inserted in decreasing order by size
  2. Go through the items in sorted order
    1. Try to place the item in the fullest bin that will accommodate it, i.e., the one that will leave the least space remaining
    2. If no bin is found, start a new bin
unsigned int best_fit_decreasing(unsigned int binsize, unsigned int *sizes, unsigned int *bins,
        unsigned int numitems)
{
    sort_uints_decreasing(sizes, numitems);
    return best_fit(binsize, sizes, bins, numitems);
}

The results were exactly the same as for First Fit Decreasing.

Worst Fit Decreasing (WFD)

This is Worst Fit after sorting.

  1. Sort the items to be inserted in decreasing order by size
  2. Go through the items in sorted order
    1. Try to place the item in the least full bin that will accommodate it, i.e., the one that will leave the most space remaining
    2. If no bin is found, start a new bin
unsigned int worst_fit_decreasing(unsigned int binsize, unsigned int *sizes, unsigned int *bins,
        unsigned int numitems)
{
    sort_uints_decreasing(sizes, numitems);
    return worst_fit(binsize, sizes, bins, numitems);
}

The results look exactly the same as the other offline algorithms, but examining the order of packing shows that item #10 and item #11 were packed the opposite way round, because there was more space in bin 5 when item #10 was packed. The end result is the same because the items are the same size.

6 bins were used
Item #0 (size 9) is in bin 0
Item #1 (size 8) is in bin 1
Item #2 (size 7) is in bin 2
Item #3 (size 6) is in bin 3
Item #4 (size 5) is in bin 4
Item #5 (size 5) is in bin 4
Item #6 (size 4) is in bin 3
Item #7 (size 4) is in bin 5
Item #8 (size 3) is in bin 5
Item #9 (size 3) is in bin 2
Item #10 (size 2) is in bin 5
Item #11 (size 2) is in bin 1
Item #12 (size 1) is in bin 0
Item #13 (size 1) is in bin 5

Conclusion

That concludes out tour of approximate bin-packing algorithms. The offline algorithms we’ve seen very often produce optimal results, but that hasn’t prevented a great deal of research on optimal algorithms. A new technique called Bin Completion (Korf, 2002) is believed to be the fastest known optimal algorithm.

References

Feature Column from the AMS: Bin Packing
Bin Packing Algorithms
A New Algorithm for Optimal Bin Packing, Richard E Korf