The Cutting-Stock Approach to Bin Packing: Theory and Experiments

摘要

We report on an experimental study of the Gilmore-Gomory cutting-stock heuristic and related LP-based approaches to bin packing, as applied to instances generated according to discrete distributions. No polynomial running time bound is known to hold for the Gilmore-Gomory approach, and empirical operation counts suggest that no straightforward implementation can have average running time O(m~3), where m is the number of distinct item sizes. Our experiments suggest that by using dynamic programming to solve the unbounded knapsack problems that arise in this approach, we can robustly obtain average running times that are o(m~4) and feasible for m well in excess of 1,000. This makes a variant on the previously un-implemented asymptotic approximation scheme of Fernandez de la Vega and Lueker practical for arbitrarily large values of m and quite small values of ε. We also observed two interesting anomalies in our experimental results: (1) running time decreasing as the number n of items increases and (2) solution quality improving as running time is reduced and an approximation guarantee is weakened. We provide explanations for these phenomena and characterize the situations in which they occur.