PACKING CONVEX HOMOTHETIC POLYTOPES INTO A CUBOID

Authors

Yu. G. Stoyan, A. Podgorny Institute of Mechanical Engineering Problems of NASU (2/10, Pozharsky str., Kharkiv, 61046, Ukraine), e-mail:  stoyan@ipmach.kharkov.ua, ORCID: 0000-0002-8053-0276

A. M. Chugay, A. Podgorny Institute of Mechanical Engineering Problems of NASU (2/10, Pozharsky str., Kharkiv, 61046, Ukraine), ORCID: 0000-0002-4079-5632

Abstract

This paper deals with the optimization problem of packing a given set of homothetical arbitrarily oriented convex polytopes without their overlapping in a linear parallelepiped of minimal volume. Phi-functions are proposed to be used as a constructive means of the mathematical modeling of a given problem. On the basis of the phi-function a mathematical model of the problem is constructed for two convex non-oriented polytopes, and its main properties which influence the choice of the strategy for solving the problem are examined. The obtained mathematical model presents the problem in the form of a classical problem of nonlinear programming, which makes it possible to use modern solvers for searching for a solution. Effective methods for finding valid starting points and locally optimal solutions based on homothetic transformations are proposed. To search for local extrema of the formulated optimization problems, a special method of decomposition has been developed, which allows us to significantly reduce computational costs due to a considerable reduction in the number of inequalities. The key idea of the optimization procedure allows us to generate subsets of the domain of admissible solutions at each stage of searching for a local extremum. Parallel computations were used to search for local extrema, which made it possible to reduce time expenditures. Numerical examples are given. The methods proposed in the work can be used for solving the problem of packaging convex polytopes.

Keywords: packing, homothetic polytopes, rotations, optimization, phi-functions

Full text: Download in PDF

References

1. Petrov, M. S., Gaidukov, V. V., & Kadushnikov, R. M. (2004). Numerical method for modeling the microstructure of granular. Materials Powder Metallurgy and Metal Ceramics, no. 43 (7–8), pp. 330–335. https://doi.org/10.1023/B:PMMC.0000048126.87171.f9
2. Wang, Y., Lin, C. L., & Miller, J. D. (2016). 3D image segmentation for analysis of multi-size particles in a packed particle bed. Powder Technology, no. 301, pp. 160–168. https://doi.org/10.1016/j.powtec.2016.05.012
3. Verkhoturov, M., Petunin, A., Verkhoturova, G., Danilov, K., & Kurennov, D. (2016). The 3D object packing problem into a parallelepiped container based on discrete-logical representation. IFAC-PapersOnLine, no. 49(12), pp. 1–5. https://doi.org/10.1016/j.ifacol.2016.07.540
4. Karabulut, K. A. & İnceoğlu, M. (2004). Hybrid genetic algorithm for packing in 3D with deepest bottom left with fill method. Advances in Information Systems, no. 3261, pp. 441–450. https://doi.org/10.1007/978-3-540-30198-1_45
5. Cao, P., Fan, Z., Gao, R., & Tang, J. (2016). Complex housing: modeling and optimization using an improved multi-objective simulated annealing algorithm. ASME Proceedings, no. 60563, V02BT03A034. https://doi.org/10.1115/DETC2016-60563
6. Guangqiang, L. A., Fengqiang, Z., Rubo, Z., Du, J., Chen, G., & Yiran, Z. (2016). Parallel particle bee colony algorithm approach to layout optimization. Journal Computational and Theoretical Nanoscience, no. 13 (7), pp. 4151–4157. https://doi.org/10.1166/jctn.2016.5263
7. Torczon, V. & Trosset, M. (1998). From evolutionary operation to parallel direct search: pattern search algorithms for numerical optimization. Computing Sci. and Statistics, no. 29, pp. 396–401.
8. Birgin, E. G., Lobato, R. D., & Martіnez, J. M. (2016). Packing ellipsoids by nonlinear optimization. Journal of Global Optimization, no. 65, pp. 709–743. https://doi.org/10.1007/s10898-015-0395-z
9. Stoyan, Y., Pankratov, A., & Romanova, T. (2016). Quasi-phi-functions and optimal packing of ellipses. Journal of Global Optimization, no. 65 (2), pp. 283–307. https://doi.org/10.1007/s10898-015-0331-2
10. Fasano, G. A. (2013). Global optimization point of view to handle non-standard object packing problems. Journal of Global Optimization, no. 55(2), pp. 279 –299. https://doi.org/10.1007/s10898-012-9865-8
11. Egeblad, J., Nielsen, B. K., & Brazil, M. (2009). Translational packing of arbitrary polytopes. Computational Geometry, no. 42 (4), pp. 269–288. https://doi.org/10.1016/j.comgeo.2008.06.003
12. Liu, X., Liu, J., Cao, A., & Yao, Z. (2015). HAPE3D – a new constructive algorithm for the 3D irregular packing problem. Frontiers of Information Technology & Electronic Engineering, no. 16 (5), pp. 380–390. https://doi.org/10.1631/FITEE.1400421
13. Youn-Kyoung, Joung & Sang, Do Noh. (2014). Intelligent 3D packing using a grouping algorithm for automotive container engineering. Journal of Computational Design and Engineering, no. 1 (2), pp. 140–151. https://doi.org/10.7315/JCDE.2014.014
14. Kallrath, J. (2016). Packing ellipsoids into volume-minimizing rectangular boxes. Journal of Global Optimization, no. 67 (1–2), pp. 151–185. https://doi.org/10.1007/s10898-015-0348-6
15. Stoyan, Y. G. & Chugay, A. M. (2014). Packing different cuboids with rotations and spheres into a cuboid. Advances in Decision Science, vol. 2014, article ID 571743. https://doi.org/10.1155/2014/571743
16. Stoyan, Y. G., Semkin, V. V., & Chugay, A. M. (2016). Modeling close packing of 3D objects. Cybernetics and Systems Analysis, no. 52 (2), pp. 296–304. https://doi.org/10.1007/s10559-016-9826-1
17. Pankratov, O., Romanova T., Stoyan Y., & Chuhai, A. (2016). Optimization of packing polyhedra in spherical and cylindrical containers. Eastern-European Journal of Enterprise Technologies, vol. 1, no. 4 (79), pp. 39–47. https://doi.org/10.15587/1729-4061.2016.60847
18. Stoyan, Y. & Yaskov, G. (2014). Packing unequal circles into a strip of minimal length with a jump algorithm. Optimization Letters, no. 8 (3), pp. 949–970. https://doi.org/10.1007/s11590-013-0646-1
19. Stoyan, Y. G. & Chugay, A. M. (2016). Mathematical modeling of the interaction of non-oriented convex polytopes. Cybernetic Systems Analysis, vol. 48, pp. 837–845. https://doi.org/10.1007/s10559-012-9463-2

Received 17 January 2018

Published 30 June 2018