« Previous post: How to install FreeBSD on a Thinkpad … — Next post: Wine + CUPS »

Introduction

The bin packing problem is the problem of packing various objects of certain sizes into a minimum number of bins with a fixed size (where the bin size is usually smaller than the sum of all objects). If you have helped someone moving out you already know something about the bin packing problem:

1. It is easy to state (“Just pack everything as tight as possible”).
2. It is hard to solve (“Dude, why is this box half-empty?”).

In fact, the problem is “NP-hard”. In order to solve it quickly, some heuristics have been found. The simplest heuristic is the Next-Fit heuristic. It works like this:

1. Keep one bin open.
2. Go through the objects.
3. As long as the object fits in the bin, pack it there. If it does not fit anymore, open a new bin.

Again, if you have ever helped someone moving out, this is the approach most people prefer to take when packing stuff. The interesting thing about this heuristic is that it is only twice as big as the optimal solution (in the worst case).

Being nerds, we are not content with this solution. Luckily, many other heuristics have been developed. I have analyzed and implemented some of them, namely:

• Best-Fit
• First-Fit
• First-Fit-Decreasing
• Max-Rest (also known as Worst-Fit)
• Next-Fit
• Next-Fit-Decreasing

Code

I have written a demo program that compares the running time and quality of the heuristics mentioned before. The program is released under a BSD licence. Please find it on GitHub. Basic usage:

make
./bin-packing < bin-packing-demo

As you can see, the input is read directly from STDIN. The input file must obey a very easy format:

• The first line must contain the number of objects as integer
• The second line must contain the bin size as an integer
• The following lines must contain the size of each object as an integer (one line per object)

The file is not checked for consistency or anything. It’s just a demo, after all.

You can generate your own input data by using the perl script generate-problem.pl. It simply generates random object data and writes it to STDOUT. The script expects two command-line parameters, namely the number of objects followed by the bin size:

perl generate-problem.pl 10000 100 > my-problem

The line above generates a random problem that contains 10000 objects varying in sizes between 1 and 100.

Analysis of the Heuristics

I have analyzed the running time and quality of the heuristics for some example files (provided by my course instructors). I do not know whether I am allowed to publish them, so I will just publish my “results”. Feel free to download my paper; it contains a short description of each heuristic along with a very basic complexity analysis. For some of the heuristics, I also prove the quality of the resulting solution (the proofs are very basic, so don’t be disappointed).