Abstract.
Higher-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. In the context of a branch-and-bound framework for solving these packing problems to optimality, it is of crucial importance to have good and easy bounds for an optimal solution. Previous efforts have produced a number of special classes of such bounds. Unfortunately, some of these bounds are somewhat complicated and hard to generalize. We present a new approach for obtaining classes of lower bounds for higher-dimensional packing problems; our bounds improve and simplify several well-known bounds from previous literature. In addition, our approach provides an easy framework for proving correctness of new bounds. This is the second in a series of four articles describing new approaches to higher-dimensional packing.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Additional information
Acknowledgment. We thank an anonymous referee for comments that helped in preparing the final version of this paper.
A previous extended abstract version of this paper appears in Algorithms–ESA’97 [2].
Supported by the German Federal Ministry of Education, Science, Research and Technology (BMBF, Förderkennzeichen 01 IR 411 C7).
Manuscript received: June 2003/Final version received: March 2004
Rights and permissions
About this article
Cite this article
Fekete, S., Schepers, J. A General Framework for Bounds for Higher-Dimensional Orthogonal Packing Problems. Math Meth Oper Res 60, 311–329 (2004). https://doi.org/10.1007/s001860400376
Issue Date:
DOI: https://doi.org/10.1007/s001860400376