Determining an upper bound for a class of rectangular packing problems (Q1086163)

Solutions to the two-dimensional, rectangular orthogonal packing problem rarely guarantee optimality, as exact algorithms require a prohibitive amount of computing time. A means of calculating the maximum number of boxes which can be fitted would be useful, both as a measure of optimality, and as an aspiration level. Existing estimates are accurate for approximately 15\% of problems typically encountered in pallet loading applications. This paper discusses a technique for reducing the loading area before applying these estimates and shows that their effectiveness can be increased to provide an exact solution for over 70\% of a random data sample.