New lower bounds for the three-dimensional orthogonal bin packing problem

In this paper, we consider the three-dimensional orthogonal bin packing problem, which is a generalization of the well-known bin packing problem. We present new lower bounds for the problem from a combinatorial point of view and demonstrate that they theoretically dominate all previous results from the literature. The comparison is also done concerning asymptotic worst-case performance ratios. The new lower bounds can be more efficiently computed in polynomial time. In addition, we study the non-oriented model, which allows items to be rotated.

► We propose new lower bounds that dominate all lower bounds from the literature. ► We present a strictly better example to emphasize the difference between the bounds. ► The asymptotic worst-case performance ratios of the lower bounds are provided. ► We also study the non-oriented model and present new lower bounds.