Development of efficient algorithms for optimal ellipse packing
DOI:
https://doi.org/10.15587/1729-4061.2014.28015Keywords:
packing, ellipses, approximation, continuous rotations, phi-functions, mathematical model, nonlinear optimizationAbstract
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.
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.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2014 Александр Викторович Панкратов, Татьяна Евгеньевна Романова, Ирина Александровна Суббота
This work is licensed under a Creative Commons Attribution 4.0 International License.
The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.
A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.
