The bin packing problem is one of the classic NP-hard combinatorial optimization problems. Given a set of n items with positive sizes, the objective is to find a packing in bins of equal capacity to minimize the number of bins required. The problem finds obvious practical usage in many industrial applications, such as the container loading problem and the cutting stock problem. There are also many variations of the bin packing problem, such as the strip packing, square packing and rectangular box packing problems.
The bin packing problem is strongly NP-hard. In order to evaluate the quality of approximation algorithms for this NP-hard problem, a considerable amount of research has been devoted to the design and analysis of lower bounds for the bin packing problem based on combinatorial approaches and dual feasible functions. On the other hand, the problem can be considered in a more general case, the non-oriented model of the multi-dimensional bin packing problem, where rotation of each given item by 90° is allowed. However, compared to the traditional oriented model, which assumes that the orientation of the given items is fixed, there is a dearth of research on this problem, especially on multi-dimensional models.
We have considered the three-dimensional orthogonal bin packing problem [1, 2] and proposed new lower bounds for the problem from a combinatorial point of view. We have also proved the tight worst-case performance ratios and provided a strictly better example. To the best of our knowledge, this is the first study to present better worst-case performance ratios than that of the continuous lower bound for the oriented three-dimensional bin packing problem. In addition, the new lower bounds can be more efficiently computed in polynomial time. We have also presented the lower bound for the non-oriented three-dimensional model, which dominates previous results from the literature. From a theoretical point of view, these new lower bounds may lead to approximation algorithms with better ratios. A better approximation algorithm for the three-dimensional orthogonal bin packing problem based on the key concept of our lower bounds would be of interest.
Finally, the beta version of our tool for computing the lower bounds and heuristic solutions is available freely for non-commercial purposes on request (download).
1. Chung-Shou Liao and Chia-Hong Hsu. New Lower Bounds for the Three-dimensional Orthogonal Bin Packing Problem, European Journal of Operational Research, published online (2012); Vol. 225(2), (2013) pp. 244-252.
2. Chia-Hong Hsu and Chung-Shou Liao. New lower bounds for the three-dimensional orthogonal bin packing problem, in Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), Toronto, Canada, pp. 381-386.