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

Development of efficient algorithms for optimal ellipse packing

Александр Викторович Панкратов, Татьяна Евгеньевна Романова, Ирина Александровна Суббота

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.


Keywords


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

References


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.


GOST Style Citations


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

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

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

Vickers, G. T. Nested Ellipses [Text] / G. T. Vickers // Applied Probability Trust. – 2009. – Vol. 41(3). – P. 131-137.

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

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

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

Панкратов, А. В. Оптимальная упаковка эллипсов с учетом допустимых расстояний [Текст] / А. В. Панкратов, Т. Е. Романова, И. А. Суббота // Журнал Обчислювальної Математики. – 2014. – T. 1 – C. 27-42.

Стоян, Ю. Г Квази-phi-функции для математического моделирования отношений геометрических объектов [Текст] / Ю. Г. Стоян, А. В. Панкратов, Т. Е. Романова, Н. И. Чернов // Доповіді Національної академії наук України. – 2014. – T. 9. – C. 49-54.

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

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

Bennell, J. Optimal clustering of a pair of irregular objects [Text] / J. Bennell, G. Scheithauer, Y. Stoyan, T. Romanova, and A. Pankratov // Journal of Global Optimization. – 2014. doi:10.1007/S10898-014-0192-0

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







Copyright (c) 2014 Александр Викторович Панкратов, Татьяна Евгеньевна Романова, Ирина Александровна Суббота

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

ISSN (print) 1729-3774, ISSN (on-line) 1729-4061