# Analysing some bin packing heuristics

# 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:

- It is easy to state (“Just pack everything as tight as possible”).
- 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:

- Keep one bin open.
- Go through the objects.
- 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).