Heuristic Solution of Open Bin Packing Problems

Benchmark problems should be hard. I report on the solution of the five open benchmark problems introduced by Falkenauer in this journal for testing bin packing problems. Since the solutions were found either by hand or by using very simple heuristic methods, these problems would appear to be easy. In four cases I give improved packings to refute conjectures that previously reported packings were optimal, and I give a proof that the fifth conjecture was correct. In some cases this led to implemented heuristic methods which produced better solutions than those reported by Falkenauer and up to 10,000 times faster. Future experimenters should be careful to perform tests on problems that can reasonably be regarded as hard.