A Computational Study of Lower Bounds for the Two Dimensional Bin Packing Problem

We survey lower bounds for the variant of the two-dimensional bin packing problem where items cannot be rotated. We prove that the dominance relation claimed by Carlier et al. [Carlier, J., F. Clautiaux and A. Moukrim, New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation, Computers and Operations Research 34 (2007), pp. 2223–2250] between their lower bounds and those of Boschetti and Mingozzi [Boschetti, M. and A. Mingozzi, The two-dimensional finite bin packing problem part I: New lower bounds for the oriented case, 40R 1 (2003), pp. 27–42] is not valid. We analyze the performance of lower bounds from the literature and we provide the results of a computational experiment.