×

Optimal rectangle packing. (English) Zbl 1201.90172

Summary: We consider the NP-complete problem of finding an enclosing rectangle of minimum area that will contain a given a set of rectangles. We present two different constraint-satisfaction formulations of this problem. The first searches a space of absolute placements of rectangles in the enclosing rectangle, while the other searches a space of relative placements between pairs of rectangles. Both approaches dramatically outperform previous approaches to optimal rectangle packing. For problems where the rectangle dimensions have low precision, such as small integers, absolute placement is generally more efficient, whereas for rectangles with high-precision dimensions, relative placement will be more effective. In two sets of experiments, we find both the smallest rectangles and squares that can contain the set of squares of size \(1\times 1, 2\times 2,\dots ,N\times N\), for \(N\) up to 27. In addition, we solve an open problem dating to 1966, concerning packing the set of consecutive squares up to \(24\times 24\) in a square of size \(70\times 70\). Finally, we find the smallest enclosing rectangles that can contain a set of unoriented rectangles of size \(1\times 2, 2\times 3, 3\times 4,\dots ,N\times (N+1)\), for \(N\) up to 25.

MSC:

90C27 Combinatorial optimization

Software:

Chaff
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Armando, A., Castellini, C., & Giunchiglia, E. (1999). SAT-based procedures for temporal reasoning. In Proceedings of the 5th European conference on planning (ECP-1999) (pp. 97–108). · Zbl 1098.68693
[2] Beldiceanu, N., & Carlsson, M. (2001). Sweep as a generic pruning technique applied to the non-overlapping rectangles constraints. In Proceedings of the principles and practice of constraint programming (CP 2001) (pp. 377–391). · Zbl 1067.68612
[3] Beldiceanu, N., Carlsson, M., Poder, E., Sadek, R., & Truchet, C. (2007). A generic geometrical constraint kernel in space and time for handling polymorphic k-dimensional objects. In Proceedings of the principles and practice of constraint programming (CP 2007) (pp. 180–194).
[4] Beldiceanu, N., Carlsson, M., & Thiel, S. (2006). Sweep synchronization as a global propagation mechanism. Computers and Operations Research, 33(10), 2835–2851. · Zbl 1113.68097
[5] Bitner, J., & Reingold, E. (1975). Backtrack programming techniques. Communications of the ACM, 18(11), 655. · Zbl 0313.68026
[6] Chan, H., & Markov, I. L. (2003). Symmetries in rectangular block-packing. In Workshop notes of the 3rd international workshop on symmetry in constraint satisfaction problems (SymCon 2003).
[7] Chan, H., & Markov, I. (2004). Practical slicing and non-slicing block-packing without simulated annealing. In ACM Great lakes symposium on VLSI (GLSVLSI04) (pp. 282–287).
[8] Clautiaux, F., Carlier, J., & Moukrim, A. (2007). A new exact method for the two-dimensional orthogonal packing problem. European Journal of Operational Research, 183(3), 1196–1211. · Zbl 1135.90045
[9] Clautiaux, F., Jouglet, A., Carlier, J., & Moukrim, A. (2008). A new constraint programming approach for the orthogonal packing problem. Computers and Operations Research, 35(3), 944–959. · Zbl 1278.90147
[10] Dechter, R., Meiri, I., & Pearl, J. (1991). Temporal constraint networks. Artificial Intelligence, 49(1-3), 61–95. · Zbl 0737.68070
[11] Dutertre, B., & de Moura, L. M. (2006). A fast linear-arithmetic solver for DPLL(T). In Proceedings of the 18th international conference on computer aided verification (CAV-2006) (pp. 81–94).
[12] Fekete, S. P., & Schepers, J. (2004a). A combinatorial characterization of higher-dimensional orthogonal packing. Mathematics of Operations Research, 29(2), 353–368. · Zbl 1082.90095
[13] Fekete, S., & Schepers, J. (2004b). A general framework for bounds for higher-dimensional orthogonal packing problems. Mathematical Methods of Operations Research, 60, 311–329. · Zbl 1076.90049
[14] Fekete, S., Schepers, J., & Ween, J. V. D. (2007). An exact algorithm for higher-dimensional orthogonal packing. Operations Research, 55(3), 569–587. · Zbl 1167.90483
[15] Gardner, M. (1975). The problem of mrs. Perkin’s quilt and other square-packing problems. In Mathematical carnival (pp. 139–149). New York: Alfred A. Knopf.
[16] Gardner, M. (1979). Mathematical games. Scientific American, 241, 18–22.
[17] Garey, M., & Johnson, D. (1979). Computers and intractability: A guide to the theory of NP-completeness. San Francisco: Freeman. · Zbl 0411.68039
[18] Gent, I. P., & Smith, B. M. (2000). Symmetry breaking in constraint programming. In Proceedings of the 14th European conference on artificial intelligence (ECAI-2000) (pp. 599–603).
[19] Guo, P. N., Cheng, C. K., & Yoshimura, T. (1999). An O-tree representation of non-slicing floorplan and its applications. In Proceedings of the 36th design automation conference (DAC 1999) (pp. 268–273).
[20] Khatib, L., Morris, P., Morris, R., & Rossi, F. (2001). Temporal constraint reasoning with preferences. In Proceedings of the 17th international joint conference on artificial intelligence (IJCAI-2001) (pp. 322–327).
[21] Korf, R. (2001). A new algorithm for optimal bin packing. In Proceedings of the national conference on artificial intelligence (AAAI-02) (pp. 731–736). Edmonton: AAAI Press.
[22] Korf, R. (2003). Optimal rectangle packing: Initial results. In Proceedings of the thirteenth international conference on automated planning and scheduling (ICAPS 2003) (pp. 287–295). Trento: AAAI Press.
[23] Korf, R. (2004). Optimal rectangle packing: New results. In Proceedings of the fourteenth international conference on automated planning and scheduling (ICAPS 2004) (pp. 142–149). Whistler: AAAI Press.
[24] Liao, Y., & Wong, C. K. (1983). An algorithm to compact a VLSI symbolic layout with mixed constraints. In Proceedings of IEEE transactions on CAD (Vol. 2).
[25] Martello, S., Pisinger, D., & Vigo, D. (2000). The three-dimensional bin packing problem. Operations Research, 48, 256–267. · Zbl 1106.90371
[26] Martello, S., & Toth, P. (1990). Lower bounds and reduction procedures for the bin packing problem. Discrete Applied Mathematics, 28, 59–70. · Zbl 0704.90074
[27] Moffitt, M. D., Peintner, B., & Pollack, M. E. (2005). Augmenting disjunctive temporal problems with finite-domain constraints. In Proceedings of the 20th national conference on artificial intelligence (AAAI-2005) (pp. 1187–1192).
[28] Moffitt, M., & Pollack, M. (2006). Optimal rectangle packing: A meta-csp approach. In Proceedings of the sixteenth international conference on automated planning and scheduling (ICAPS 2006). Cumbria: AAAI Press.
[29] Moskewicz, M. W., Madigan, C. F., Zhao, Y., Zhang, L., & Malik, S. (2001). Chaff: Engineering an efficient SAT solver. In Proceedings of the 38th design automation conference (DAC 2001) (pp. 530–535).
[30] Murata, H., Fujiyoshi, K., Nakatake, S., & Kajitani, Y. (1995). Rectangle-base module placement. In Proceedings of the international conference on computer-aided design (ICCAD95) (pp. 472–479).
[31] Nakatake, S., Fujiyoshi, K., Murata, H., & Kajitani, Y. (1996). Module placement on bsg-structure and ic layout applications. In Proceedings of the international conference on computer-aided design (ICCAD96) (pp. 484–491).
[32] Oddi, A., & Cesta, A. (2000). Incremental forward checking for the disjunctive temporal problem. In Proceedings of the 14th European conference on artificial intelligence (ECAI-2000) (pp. 108–112).
[33] Onodera, H., Taniguchi, Y., & Tamaru, K. (1991). Branch-and-bound placement for building-block layout. In Proceedings of the ACM design automation conference (DAC91) (pp. 433–439).
[34] Scheithauer, G. (1998). Equivalence and dominance for problems of optimal packing of rectangles. Ricerca Operativa, 83, 3–34.
[35] Sheini, H. M., & Sakallah, K. A. (2006). From propositional satisfiability to satisfiability modulo theories. In Proceedings of the 9th international conference on theory and applications of satisfiability testing (SAT-2006) (pp. 1–9). · Zbl 1187.68567
[36] Stergiou, K., & Koubarakis, M. (1998). Backtracking algorithms for disjunctions of temporal constraints. In Proceedings of the 15th national conference on artificial intelligence (AAAI-1998) (pp. 248–253). · Zbl 0945.68038
[37] Tsamardinos, I., & Pollack, M. E. (2003). Efficient solution techniques for disjunctive temporal reasoning problems. Artificial Intelligence, 151(1-2), 43–90. · Zbl 1082.68825
[38] Watson, G. (1918). The problem of the square pyramid. Messenger of Mathematics, New Series, 48, 1–22. · JFM 46.0213.01
[39] Young, E. F. Y., Chu, C. C. N., & Ho, M. L. (2002). A unified method to handle different kinds of placement constraints in floorplan design. In 15th international conference on VLSI design (VLSI design 2002) (pp. 661–667).
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.