SOLUTION TO THE PROBLEM OF OPTIMAL PACKING OF HOMOTHETIC ELLIPSOIDS IN A CONTAINER OF MINIMUM VOLUME

DOI https://doi.org/10.15407/pmach2016.02.044
Journal Journal of Mechanical Engineering – Problemy Mashynobuduvannia
Publisher A. Podgorny Institute for Mechanical Engineering Problems
National Academy of Science of Ukraine
ISSN 0131-2928 (Print), 2411-0779 (Online)
Issue Vol. 19, no. 2, 2016 (June)
Pages 44-49
Cited by J. of Mech. Eng., 2016, vol. 19, no. 2, pp. 44-49

 

Authors

O. M. Khlud, A. Podgorny Institute of Mechanical Engineering Problems of NASU (2/10, Pozharsky St., Kharkiv, 61046, Ukraine), e-mail: hlud.olga@mail.ru

 

Abstract

The problem of optimizing the packing of homothetic equally oriented ellipsoids is considered. A mathematical model is constructed in the form of a nonlinear programming problem. An algorithm for finding locally optimal solutions using homothetic transformations of ellipsoids and an optimization procedure is proposed. The procedure makes it possible to reduce the problem with a large number of inequalities to a sequence of problems with a smaller number of inequalities. The results of numerical experiments are given.

 

Keywords: optimal packing, homothetic ellipsoids, phi-functions, start points, nonintersection, inclusion, nonlinear programming, iterative procedure, LOFRT procedure

 

References

  1. Wright, S. J. (2013). Packing ellipsoids with overlap. SIAM Review, vol. 55(4), pp. 671–706. https://doi.org/10.1137/120872309
  2. Kallrath, J. (2015). Packing ellipsoids into volume-minimizing rectangular boxes. Journal of Global Optimization, pp. 1–32. https://doi.org/10.1007/s10898-015-0348-6.
  3. Pankratov, A., Romanova, T., & Khlud, O. (2015). Quasi-phi-functions in packing of ellipsoids. Radioelectronics & Informatics, vol. 68, pp. 37–42.
  4. Lubachevsky, B. D. & Stillinger, F. H. (1990). Geometric properties of random disk packings. Journal of Statistical Physics, vol. 60, no. 5–6, pp. 561–583. https://doi.org/10.1007/BF01025983
  5. Bennell, J.  & Oliveira, J. F. (2009). A tutorial in irregular shape packing problem. Journal of the Operational Research Society, vol. 60, pp. 93–105. https://doi.org/10.1057/jors.2008.169
  6. Chernov, N., Stoyan, Yu., & Romanova, T. (2010). Mathematical model and efficient algorithms for object packing problem. Computational Geometry: Theory and Applications, vol. 43, no. 5, pp. 533–553. https://doi.org/10.1016/j.comgeo.2009.12.003
  7. Stetsuk, P., Romanova, T. E., & Subota, I. O. (2014). NLP-zadacha upakovky homotetychnyh elipsiv u priamokutnyi konteiner. Teoriya optymalnyh rishen: zb. nauk. pr., In. kibernetyky im. V. M. Hkushkova NAN Ukrainy, Kyiv, pp. 139–146.
  8. Stoyan, Yu.  & Yaskov, G. N. (2004). A mathematical model and a solution method for the problem of placing various-sized circles into a strip. European Journal of Operational Research, vol. 156, pp. 590–600. https://doi.org/10.1016/S0377-2217(03)00137-1
  9. Stoyan, Y., Pankratov, A., & Romanova, T. (2015). Quasi-phi-functions and optimal packing of ellipses. Journal of Global Optimization, vol. 65, pp. 283–307. https://doi.org/10.1007/s10898-015-0331-2

 

Received 03 April 2016

Published 30 June 2016