Development of efficient algorithms for optimal ellipse packing

Authors

  • Александр Викторович Панкратов A. N. Podgorny Institute for Mechanical Engineering Problems NAS of Ukraine Dm. Pozharsky 2/10, Kharkiv, 61046, Ukraine https://orcid.org/0000-0002-2958-8923
  • Татьяна Евгеньевна Романова A. N. Podgorny Institute for Mechanical Engineering Problems NAS of Ukraine Dm. Pozharsky 2/10, Kharkiv, 61046, Ukraine https://orcid.org/0000-0002-8618-4917
  • Ирина Александровна Суббота A. N. Podgorny Institute for Mechanical Engineering Problems NAS of Ukraine Dm. Pozharsky 2/10, Kharkiv, 61046, Ukraine

DOI:

https://doi.org/10.15587/1729-4061.2014.28015

Keywords:

packing, ellipses, approximation, continuous rotations, phi-functions, mathematical model, nonlinear optimization

Abstract

The problem of packing a set of ellipses, allowing continuous rotations in a minimum size container is considered. For describing nonoverlapping and containment constraints, phi-functions are used for ellipses approximated by circle arcs. A mathematical model is constructed in the form of a non-smooth optimization problem. Algorithms for finding locally optimal solutions to the problem of packing approximated ellipses, based on the construction of a decision tree, the end vertices of which correspond to a system of inequalities with continuously differentiable functions are proposed. Three strategies for solving the problem of optimal packing true ellipses are considered. The first strategy allows to find approximate solutions for packing ellipses in rectangular, circular and elliptic containers. Locally optimal solutions for packing ellipses in a rectangular container can be obtained by applying the second and third strategies. The examples of challenge benchmark instances) for  ellipses are given.

Author Biographies

Александр Викторович Панкратов, A. N. Podgorny Institute for Mechanical Engineering Problems NAS of Ukraine Dm. Pozharsky 2/10, Kharkiv, 61046

Doctor of Technics, senior scientist

Department for Mathematical Modeling

Татьяна Евгеньевна Романова, A. N. Podgorny Institute for Mechanical Engineering Problems NAS of Ukraine Dm. Pozharsky 2/10, Kharkiv, 61046

Doctor of Technics, senior scientist

Department for Mathematical Modeling

Ирина Александровна Суббота, A. N. Podgorny Institute for Mechanical Engineering Problems NAS of Ukraine Dm. Pozharsky 2/10, Kharkiv, 61046

Aspirant

Department for Mathematical Modeling

References

  1. Toth, L. F. (1986). Packing of ellipses with continuously distributed area. Journal of Discrete Mathematics, Vol. 60, 263–267. doi:10.1016/0012-365X(86)90018-X.

    Ting, J. M., Khwaja, M., Meachum, L. R., Rowell, J. D. (1993). An ellipse-based discrete element model for granular materials. Numerical and Analytical Methods in Geomechanics, Vol. 17 (9), 603–623. doi:10.1002/nag.1610170902.

    Feng, Y., Han, K., Owen, D. (2002). An Advancing Front Packing of Polygons, Ellipses and Spheres. Discrete Element Methods, 93-98. doi:10.1061/40647(259)17.

    Vickers, G. T. (2009). Nested Ellipses. Applied Probability Trust, Vol. 41(3), 131–137.

    Xu, W. X., Chen, H. S., Lv, Z. (2011). An overlapping detection algorithm for random sequential packing of elliptical particles. Physica, Vol. 390, 2452–2467. doi:10.1016/j.physa.2011.02.048.Birgin, E. G., Bustamante, L. H., Callisaya, H. F., Martınez, J. M. (2013). Packing circles within ellipses. International transactions in operational research, Vol. 20 (3), 365–389. doi:10.1111/itor.12006.

    Kallrath, J., Rebennack, S. (2013). Cutting Ellipses from Area-Minimizing Rectangles. Journal of Global Optimization, Vol. 59 (2-3), 405–437. doi:10.1007/s10898-013-0125-3.

    Kallrath, J. (2008). Cutting Circles and Polygons from Area-Minimizing Rectangles. Journal of Global Optimization, Vol. 43 (2-3), 299–328. doi:10.1007/s10898-007-9274-6.

    Pankratov, A., Romanova, T., Subota, I. (2014). Optimal packing problem of ellipses taking into account minimal allowable distance. Journal of Numerical Mathematics, Vol. 1, 27–42.

    Stoyan, Y., Pankratov, A., Romanova, T., Chernov, N. (2014). Quasi-phi-function for the mathematical modeling of geometric objects relationships. Reports of the National Academy of Sciences of Ukraine, Vol. 9, 49–54.

    Chernov, N., Stoyan, Y., Romanova, T., Pankratov, A. (2012). Phi-Functions for 2D Objects Formed by Line Segments and Circular Arcs. Advances in Operations Research, 26. doi:10.1155/2012/346358.

    Chernov, N, Stoyan, Y, Romanova, T. (2010). Mathematical model and efficient algorithms for object packing problem. Computational Geometry: Theory and Applications, Vol. 43 (5), 535–553. doi:10.1016/j.comgeo.2009.12.003.

    Bennell, J., Scheithauer, G., Stoyan, Y., Romanova, T., Pankratov, A. (2014). Optimal clustering of a pair of irregular objects. Journal of Global Optimization. doi:10.1007/s10898-014-0192-0.

    Wachter, A., Biegler, L. T. (2006). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, Vol. 106 (1), 25–57. doi:10.1007/s10107-004-0559-y.

Published

2014-10-21

How to Cite

Панкратов, А. В., Романова, Т. Е., & Суббота, И. А. (2014). Development of efficient algorithms for optimal ellipse packing. Eastern-European Journal of Enterprise Technologies, 5(4(71), 28–35. https://doi.org/10.15587/1729-4061.2014.28015

Issue

Section

Mathematics and Cybernetics - applied aspects