On a combinatorial structure of the problems of optimal packing of geometric objects

1Yakovlev, SV
1National Aerospace University "Zhukovskiy Kharkiv Aviation Institute"
Dopov. Nac. akad. nauk Ukr. 2017, 9:26-32
Section: Information Science and Cybernetics
Language: Russian

The problem of optimal layout of geometric objects with given shape and physico-metric parameters is considered. Combinatorial structure is allocated by forming the multiple tuples of physico-metric parameters. On the basis of a functional presentation of the permutations of tuples, an equivalent setting, in which physico-metric parameters are variables, is formulated. The proposed approach is illustrated by the problem of packing of unequal circles into a circle with minimal radius.

Keywords: combinatorial set, optimization, packing problem, tuple
  1. Che, C., Wang, Y. & Teng, H. (2008). Test problems for quasi-satellite packing: cylinders packing with behavior constraints and all the optimal solutions known. Optimization Online.
  2. Fasano, G. & Pinte'r, J. D. (Eds.): (2013). Modeling and Optimization in Space Engineering. Series: Springer Optimization and Its Applications. Vol. 73, p.404. https://doi.org/10.1007/978-1-4614-4469-5
  3. Hifi, M. & M'Hallah, R. (2009). A literature Review on Circle and Sphere Packing Problems:Model and Methodologies. Advances in Optimization Research. https://doi.org/10.1155/2009/150624
  4. Bortfeldt, A. & Wäscher, G. (2013). Constraints in container loading: a state-of-the-art review. European J. Operational Research., Vol. 229, Iss.1, pp. 1-20. https://doi.org/10.1016/j.ejor.2012.12.006
  5. Stetsyuk, P. I., Romanova, T. E. & Scheithauer, G. (2015). On the global minimum in a balanced circular packing problem // Optimization Letters. 10, Iss. 6, pp. 1347-1360.
  6. Stoyan, Yu. G., Scheithauer, G., Romanova, T. (2002). F-functions for primary 2D-objects. Studia Informatica Universalis. Int. J. Informayics. 2, pp.1-32.
  7. Chernov, N., Stoyan, Y. & Romanova, T. (2010). Mathematical model and efficient algorithms for object packing problem. Computational Geometry: Theory and Applications. Iss. 5, pp. 535-553. https://doi.org/10.1016/j.comgeo.2009.12.003
  8. Pichugina, O. S. & Yakovlev, S. V. (2016). On continuous representations and functional extensions in problems of combinatorial optimization. Cybernetics and systems analysis. No. 6, pp. 102-113.
  9. Pichugina, O. S. & Yakovlev, S. V. (2016). Functional-analytic representations of a general permutation set. Eastern-European J. Enterprise Technologie. No. 1, pp. 101-126. http://journals.uran.ua/eejet/article/view/58550
  10. Stoyan, Yu. & Yaskov, G. (2014). Packing unequal circles into a strip of minimal length with a jump algorithm. Optimization Letters, 8, Iss. 3, p. 949-970. https://doi.org/10.1007/s11590-013-0646-1
  11. Yaskov, G. N. (2014). Packing non-equal hyperspheres into a hypersphere of minimal radius. Probl. Mechanical engineering, 17, No. 2, pp. 48-53.
  12. Stoyan, Yu. G., Scheithauer, G. & Yaskov, G. N. (2016). Packing Unequal Spheres into &Various Containers. Cybernetics and Systems Analysis, 52, No. 3,·pp 419-426. https://doi.org/10.1007/s10559-016-9842-1