Bin-packing algorithms

Most of the research on bin-packing algorithms starts in the 1970s and the 1980s, in the USA. One of the noted researchers, Ron Graham, is also a talented juggler and former circus performer.

The problem of getting the best bin-packing is one of the “NP-complete” category of “intractable” problems.

(1) There is no known exact algorithm for these problems which doesn’t become unworkable (require hundreds of years or a computer bigger than the Earth, etc.) for large numbers of items.

(2) There is, however, a workable algorithm to check a proposed solution.

(3) No-one knows whether a workable exact algorithm can be devised to find a solution, rather than check one; but if if a workable exact algorithm can be devised for one of these “NP-complete” problems, then (it has been proven) a workable exact algorithm can be devised for all the other “NP-complete” problems too.

Most mathematicians think that no workable exact algorithm can be found for the “NP-complete” problems, but no-one has proved it yet. (This is called the “P-vs-NP problem”).

Quite a few common problems are also “intractable”, for example the problem of how to design a timetable for a school which avoids clashes and fits the maximum number of student preferences. All known algorithms for bin-packing are approximations which may tell us to use more bins than are necessary. Likewise, all known algorithms for timetabling are only approximations.

First fit: time of the order of N log N for N items

May give up to 2 times the optimal number of bins

First fit decreasing: workable only if we can survey all the items before packing (rather than having to pack them as they arrive)

Time of the order of N log N for sorting, plus another N log N for fitting

Uses at most (4M + 1)/3 bins if the optimal is M

Full-bin: also workable only if we can survey all the items before packing (rather than having to pack them as they arrive)

Calculation time of the order of 2N (which means over a hundred years on a modern computer for a problem with just 60 items…)

Does not necessarily give a good solution. Suppose the bins have size 12, and we have items of size 4, 7, 4, 7, 4, 7. The full-bin packing algorithm will tell us to take four bins – 4+4+4, 7, 7, and 7 – though First Fit would give us three bins, 4+7, 4+7, 4+7. (And in real life, of course, there will often be no combination of items that fills a bin exactly. I don’t know where the Edexcel book got “Full-bin” from. Not real life).

Contrary to what your textbook says, an algorithm for the best bin-packing is possible. Just try out every single combination of items and bins, and eventually you will find the best one. The problem is that for even quite small numbers of items, this try-out-every-possibility algorithm involves too much calculation to be workable even with the fastest computer.

There are also many problems which are not computable, that is, we can prove that no algorithm exists to solve them, not even an unworkably long one. For example, this problem: find an algorithm to check equations of the type xy2-2x2+3=0 (polynomials in x and y with whole-number coefficients), and decide whether they have a whole-number solution. (For example, x2+y2=25 does, but x2+y2=24 doesn’t).

http://www.ams.org/samplings/feature-column/fcarc-bins1

https://www.cs.ucsb.edu/~suri/cs130b/BinPacking.txt

ron_graham

Ron Graham