×

Exhaustive approaches to 2D rectangular perfect packings. (English) Zbl 1170.90523

Summary: We consider the two-dimensional rectangular strip packing problem, in the case where there is a perfect packing; that is, there is no wasted space. One can think of the problem as a jigsaw puzzle with oriented rectangular pieces. Although this comprises a quite special case for strip packing, we have found it useful as a subroutine in related work. We demonstrate a simple pruning approach that makes a branch-and-bound-based exhaustive search extremely effective for problems with less than 30 rectangles.

MSC:

90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baker, B. S.; Coffman, E. G.; Rivest, R. L., Orthogonal packings in two dimensions, SIAM J. Comput., 9, 846-855 (1980) · Zbl 0447.68080
[2] Baker, B. S.; Brown, D. J.; Katseff, H. P., A 5/4 algorithm for two-dimensional packing, J. Algorithms, 2, 348-368 (1981) · Zbl 0472.68032
[3] Bitner, J. R.; Reingold, E. M., Backtrack programming techniques, Comm. ACM, 18, 11, 651-656 (1975) · Zbl 0313.68026
[4] Brown, D. J., An improved BL lower bound, Inform. Process. Lett., 11, 37-39 (1980) · Zbl 0444.68062
[5] Chazelle, B., The bottom-left bin-packing heuristic: an efficient implementation, IEEE Trans. Comput., 32, 8, 697-707 (1983) · Zbl 0526.68065
[6] Coffman, E. G.; Garey, M. R.; Johnson, D. S., Approximation algorithms for bin-packing: an updated survey, (Ausiello, G.; Lucertini, M.; Serafini, P., Algorithm Design for Computer Systems Design (1984), Springer-Verlag: Springer-Verlag Berlin), 49-106 · Zbl 0558.68062
[7] Dyckhoff, H., Typology of cutting and packing problems, European J. Oper. Res., 44, 145-159 (1990) · Zbl 0684.90076
[8] S.P. Fekete, J. Schepers, On more-dimensional packing III: exact algorithms, available as a preprint at Mathematisches Institut, Universität zu Köln, preprint key zpr97-290; S.P. Fekete, J. Schepers, On more-dimensional packing III: exact algorithms, available as a preprint at Mathematisches Institut, Universität zu Köln, preprint key zpr97-290
[9] E. Hopper, Two-dimensional packing utilising evolutionary algorithms and other meta-heuristic methods, Ph.D. thesis, Cardiff University, UK, 2000; E. Hopper, Two-dimensional packing utilising evolutionary algorithms and other meta-heuristic methods, Ph.D. thesis, Cardiff University, UK, 2000
[10] Hopper, E.; Turton, B. C.H., An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem, European J. Oper. Res., 128, 1, 34-57 (2000) · Zbl 0982.90044
[11] Iori, M.; Martello, S.; Monaci, M., Metaheuristic algorithms for the strip packing problem, (Paradolos, P. M.; Korotkith, V., Optimization and Industry: New Frontiers (2003), Kluwer Academic: Kluwer Academic Dordrecht), 159-179 · Zbl 1051.90030
[12] Kenyon, C.; Remilia, E., Approximate strip-packing, (Proceedings of the 37th Annual Symposium on Foundations of Computer Science (1996)), 31-36
[13] Korf, R. E., Optimal rectangle packing: initial results, (Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS-03), Trento, Italy (2003)) · Zbl 1172.90475
[14] N. Lesh, J. Marks, A. McMahon, M. Mitzenmacher, New exhaustive, heuristic, and interactive approaches to 2D rectangular strip packing, MERL Technical Report TR2003-05, 2003; N. Lesh, J. Marks, A. McMahon, M. Mitzenmacher, New exhaustive, heuristic, and interactive approaches to 2D rectangular strip packing, MERL Technical Report TR2003-05, 2003 · Zbl 1137.68579
[15] Lodi, A.; Martello, S.; Monaci, M., Two-dimensional packing problems: a survey, European J. Oper. Res., 141, 2, 241-252 (2003) · Zbl 1081.90576
[16] Martello, S.; Monaci, M.; Vigo, D., An exact approach to the strip packing problem, INFORMS J. Comput., 15, 3, 310-319 (2003) · Zbl 1238.90116
[17] Sleator, D., A 2.5 times optimal algorithm for packing in two dimensions, Inform. Process. Lett., 10, 37-40 (1980) · Zbl 0426.05023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.