Abstract
This paper discusses the minimal area rectangular packing problem which is to pack a given set of rectangles into a rectangular container of minimal area such that no two rectangles overlap. Current approaches for this problem rely on metaheuristics like simulated annealing, on constraint programming or on non-linear models. Difficulties arise from the non-convexity and the combinatorial complexity. We investigate different mathematical programming approaches for this and introduce a novel approach based on non-linear optimization and the “tunneling effect” achieved by a relaxation of the non-overlapping constraints. We compare our optimization algorithm to a simulated annealing and a constraint programming approach and show that our approach is competitive. Additionally, since it is easy to extend, it is also applicable to a variety of related problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ababei, C., Feng, Y., Goplen, B., Mogal, H., Bazargan, K., Sapatnekar, S. S., & Zhang, T. (2005). Placement and routing in 3D integrated circuits. IEEE Design and Test of Computers, 22(6), 520–531.
Ali, M., Törn, A., & Viitanen, S. (1997). A direct search simulated annealing algorithm for optimization involving continuous variables (Technical Report TUCS-TR-97).
Alon, A., & Ascher, U. (1988). Model and solution strategy for placement of rectangular blocks in the euclidean plane. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 7(3), 378–386.
Amossen, R. R., & Pisinger, D. (2006). Multi-dimensional bin packing problems with guillotine constraints. Computers and Operations Research.
Anagnostopoulos, A., Michel, L., Hentenryck, P., & Vergados, Y. (2006). A simulated annealing approach to the traveling tournament problem. Journal of Scheduling, 9(2), 177–193.
Bansal, N., & Sviridenko, M. (2004). New approximability and inapproximability results for 2-dimensional bin packing. In Proceedings of the fifteenth annual SIAM symposium on discrete algorithms (pp. 196–203). Philadelphia, PA, USA. Philadelphia: Society for Industrial and Applied Mathematics.
Bazaraa, M., Sherali, H. D., & Shetty, C. (1993). Nonlinear programming: theory and algorithms (2nd ed.). New York: Wiley.
Berger, M. (2006). Module placement in 2.5D system in package design automation. Master’s thesis, University of Applied Sciences, Mittweida.
Birgin, E. G., Martìnez, J. M., Nishihara, F. H., & Ronconi, D. P. (2006). Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization. Computers and Operations Research, 33(12), 3535–3548.
Blum, C., & Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35(3), 268–308.
Burke, J. V., & Xu, S. (2000). A non-interior predictor-corrector path-following algorithm for the monotone linear complementarity problem. Mathematical Programming, A87, 113–130.
Chang, Y. C., Chang, Y.-W., Wu, G. M., & Wu, S. W. (2000). B*-trees: A new representation for non-slicing floorplans. In Proceedings of the 37th conference on design automation (pp. 458–463).
Chen, B., Chen, X., & Kanzow, C. (2000). A penalized Fischer-Burmeister NCP-function. Mathematical Programming, 88(1), 211–216.
Chen, B., & Harker, P. T. (1993). A non-interior-point continuation method for linear complementarity problems. SIAM Journal on Matrix Analysis and Applications, 14(4), 1168–1190.
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.
Coffman, E. G., Garey, M. R., & Johnson, D. S. (1996). Approximation algorithms for bin packing: A survey. In D. Hochbaum (Ed.), Approximation algorithms for NP-hard problems (pp. 46–93). Boston: PWS Publishing.
Dorneich, M. C., & Sahinidis, N. V. (1995). Global optimization algorithms for chip layout and compaction. Engineering Optimization, 25(2), 131–154.
Fasano, G. (2004). A MIP approach for some practical packing problems: Balancing constraints and tetris-like items. 4OR: A Quarterly Journal of Operations Research, 2(2), 161–174.
Goetschalckx, M., & Irohara, T. (2007). Efficient formulations for the multi-floor facility layout problem with elevators. Optimization Online.
Guo, P.-N., Cheng, C.-K., & Yoshimura, T. (1999). An O-Tree representation of non-slicing floorplan and its applications. In Proceedings of the 1999 design automation conference (pp. 268–273).
Herrigel, A., & Fichtner, W. (1989). An analytic optimization technique for placement of macro-cells. In DAC ’89: Proceedings of the 26th ACM/IEEE conference on design automation (pp. 376–381). New York, NY, USA. New York: ACM Press.
Horst, R., & Tuy, H. (1996). Global optimization: deterministic approaches (3rd ed.). Heidelberg: Springer.
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598).
Kolonko, M. (1999). Some new results on simulated annealing applied to the job shop scheduling problem. European Journal of Operational Research, 113(1), 123–136.
Levy, A. V., & Montalvo, A. (1985). The tunneling algorithm for the global minimization of functions. SIAM Journal on Scientific and Statistical Computing, 6(1), 15–29.
Lin, J. M., & Chang, Y.-W. (2001). TCG: A transitive closure graph-based representation for non-slicing floorplans. In Proceedings of the 2001 design automation conference (pp. 764–769).
Luenberger, D. G. (1989). Linear and nonlinear programming. Reading: Addison-Wesley.
Moffitt, M. D., & Pollack, M. E. (2006). Optimal rectangle packing: A Meta-CSP approach. In Proceedings of the 16th international conference on automated planning and scheduling.
Murata, H., Fujiyoshi, K., Nakatake, S., & Kajitani, Y. (1996). VLSI module placement based on rectangle-packing by the sequence-pair. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 15(12), 1518–1524.
Pisinger, D. (2007). Denser packings obtained in O(n log log n) time. INFORMS Journal of Computing, 19(3), 395–405.
Rossi, F., van Beek, P., & Walsh, T. (2006). Handbook of constraint programming. Amsterdam: Elsevier B.V.
Stein, O. (2003). Bi-level strategies in semi-infinite programming. Boston: Kluwer.
Sun, D., & Qi, L. (1999). On NCP-functions. Computational Optimization and Applications, 13, 201–220.
Tang, X., Tian, R., & Wong, D. F. (2001). FAST-SP: A fast algorithm for block placement based on sequence pair. In Proceedings of the 2001 Asia and South Pacific design automation conference (pp. 521–526). New York: ACM Press.
Wang, Y.-J., & Zhang, J.-S. (2007). An efficient algorithm for large scale global optimization of continuous functions. Journal of Computational and Applied Mathematics, 206(2), 1015–1026.
Winterfeld, A. (2007). Large-scale semi-infinite optimization applied to industrial gemstone cutting. PhD thesis, University of Kaiserslautern.
Wong, D. F., & Liu, C. L. (1986). A new algorithm for floorplan design. In DAC ’86: Proceedings of the 23rd ACM/IEEE conference on design automation (pp. 101–107). Piscataway, NJ, USA. New York: IEEE Press.
Wright, S. J. (1997). Primal-dual interior-point methods. Philadelphia: SIAM.
Yao, B., Chen, H., Cheng, C.-K., & Graham, R. L. (2003). Floorplan representations: Complexity and connections. ACM Transactions on Design of Automated Electronic Systems, 8(1), 55–80.
Ye, Y. (1997). Interior point algorithms, theory and analysis. New York: Wiley.
Zhan, Y., Feng, Y., & Sapatnekar, S. S. (2006). A fixed-die floorplanning algorithm using an analytical approach. In Proceedings of the 2006 conference on Asia South Pacific design automation (pp. 771–776). New York, NY, USA. New York: ACM Press.
Zhang, J. Z., & Kim, N. H. (1985). An improved successive linear programming algorithm. Management Science, 31(10), 1312–1331.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Maag, V., Berger, M., Winterfeld, A. et al. A novel non-linear approach to minimal area rectangular packing. Ann Oper Res 179, 243–260 (2010). https://doi.org/10.1007/s10479-008-0462-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-008-0462-7