Improved bin completion for optimal bin packing and number partitioning

Abstract

The bin-packing problem is to partition a multiset of n numbers into as few bins of capacity C as possible, such that the sum of the numbers in each bin does not exceed C. We compare two existing algorithms for solving this problem: bin completion (BC) and branch-and-cut-and-price (BCP). We show experimentally that the problem difficulty and dominant algorithm are a function of n, the precision of the input elements and the number of bins in an optimal solution. We describe three improvements to BC which result in a speedup of up to five orders of magnitude as compared to the original BC algorithm. While the current belief is that BCP is the dominant bin-packing algorithm, we show that improved BC is up to five orders of magnitude faster than a state-of-the-art BCP algorithm on problems with relatively few bins. We then explore a closely related problem, the number-partitioning problem, and show that an algorithm based on improved bin packing is up to three orders of magnitude faster than a BCP solver called DIMM which claims to be state of the art. Finally, we show how to use number partitioning to generate difficult binpacking instances.