A study of ellipse packing in the high-dimensionality problems

Authors

DOI:

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

Keywords:

packing, continuous rotations, quasi-phi-functions, mathematical model, nonlinear optimization, individual-and-flow movement

Abstract

The problems of optimum ellipse packing belong to the class of NP-hard problems. The issues of development of efficient algorithms based on application of local and global optimization methods, construction of adequate mathematical models based on the analytical description of the ellipse interrelations taking into account their continuous translations and rotations are of vital importance. In this article, the problem of packing of sets of ellipses in a given region taking into account conditions of nonintersection and technological restraints which are concretized in the conditions of the applied problem is formulated. The model of packing of a set of ellipses in a rectangle of minimum dimensions is constructed. Continuous ellipse rotations and translations are allowed, the possibility of availability of minimum admissible distances between them is assumed. New quasi-phi-functions are constructed for modeling of the relations of ellipse nonintersection and to define belonging of an ellipse to the container. The algorithm of search for locally optimal solutions is modified. It consists of two stages: generation of the regions of feasibility which contain the starting point and local optimization in the constructed region of feasibility. Only the algorithm step concerning construction of quasi-phi-functions is subjected to modification. It is necessary to notice that the algorithm have shown its efficiency when the quantity of ellipses does not exceed the value of 400.

The model of the individual-and-flow movement of individuals approximated by ellipses with specification of technological restraints is constructed. The method of local optimization is given. Examples of computer modeling of the problems assigned in the work are given.

Author Biographies

Valentina Komyak, National university of civil protection of Ukraine Chernichevska str., 94, Kharkiv, Ukraine, 61023

Doctor of Technical Sciences, Professor

Department of physical and mathematical sciences

Vladimir Komyak, National university of civil protection of Ukraine Chernichevska str., 94, Kharkiv, Ukraine, 61023

PhD

Department оf management and organization of activities in the field of Civil Protection 

Alexander Danilin, National university of civil protection of Ukraine Chernichevska str., 94, Kharkiv, Ukraine, 61023

Postgraduate student

Department of physical and mathematical sciences

References

  1. Wаscher, G., Hauner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research, 183 (3), 1109–1130. doi: 10.1016/j.ejor.2005.12.047
  2. Bennell, J. A., Oliveira, J. F. (2008). The geometry of nesting problems: A tutorial. European Journal of Operational Research, 184 (2), 397–415. doi: 10.1016/j.ejor.2006.11.038
  3. Holschevnikov, V. V., Parfenenko, A. P. (2015). Comparison of different movement patterns of human flows and results of software and computer systems. Fire and explosion safety, 24 (5), 68–74.
  4. Bardadym, T. A., Berezovsky, O. A. (2013). Notes on the approaches to the construction of F-functions for the ellipses. Computer mathematics, 2, 50–56.
  5. Toth, L. F. (1986). Packing of ellipses with continuously distributed area. Discrete Mathematics, 60, 263–267. doi: 10.1016/0012-365x(86)90018-x
  6. Vickers, G. T. (2009). Nested Ellipses. Applied Probability Trust, 41 (3), 131–137.
  7. Xu, W. X., Chen, H. S., Lv, Z. (2011). An overlapping detection algorithm for random sequential packing of elliptical particles. Physica A: Statistical Mechanics and its Applications, 390 (13), 2452–2467. doi: 10.1016/j.physa.2011.02.048
  8. Birgin, E. G., Bustamante, L. H., Callisaya, H. F., Martínez, J. M. (2013). Packing circles within ellipses. International Transactions in Operational Research, 20 (3), 365–389. doi: 10.1111/itor.12006
  9. Bustamante, L. H. (2012). Stochastic global optimization strategies for packing circles within ellipses. University of Sao Paulo.
  10. Kallrath, J., Rebennack, S. (2013). Cutting ellipses from area-minimizing rectangles. Journal of Global Optimization, 59 (2-3), 405–437. doi: 10.1007/s10898-013-0125-3
  11. Kallrath, J. (2008). Cutting circles and polygons from area-minimizing rectangles. Journal of Global Optimization, 43 (2-3), 299–328. doi: 10.1007/s10898-007-9274-6
  12. Pankratov, A. V., Romanova, T. E., Subota, I. A. (2014). Optimal packaging ellipses given allowable distance. Journal of computing mathematics, 1, 27–42.
  13. Stoyan, Y., Pankratov, A., Romanova, T. (2015). Quasi-phi-functions and optimal packing of ellipses. Journal of Global Optimization, 65 (2), 283–307. doi: 10.1007/s10898-015-0331-2
  14. Stoyan, Yu., Pankratov, A., Romanova, T., Chernov, N. I. (2014). Quasi-phi-functions for mathematical modeling of geometric relations. Reports of Academy of National of Sciences of Ukraine, 9, 49–54.
  15. Stoyan, Y., Romanova, T., Pankratov, A., Chugay, A. (2015). Optimized Object Packings Using Quasi-Phi-Functions. Springer Optimization and Its Applications, 265–293. doi: 10.1007/978-3-319-18899-7_13
  16. Birgin, E. G., Lobato, R., Martínez, J. M. (2016). Packing Ellipsoids by Nonlinear Optimization. Journal of Global Optimization, 709–743.
  17. Birgin, E. G., Martínez, J. M. (2014). Practical Augmented Lagrangian Methods for Constrained Optimization. Philadelphia, PA. doi: 10.1137/1.9781611973365
  18. Danilin, A. N., Komyak, V. V., Komyak, V. M., Pankratov, A. V. (2016). Packaging ellipse in a rectangle of minimal area. USiM, 5, 5–9.
  19. Pankratov, A. V., Romanova, T. E., Subbota, I. A. (2014). Development of efficient algorithms for optimal ellipse packing. Eastern-European Journal of Enterprise Technologies, 5 (4 (71)), 28–35. doi: 10.15587/1729-4061.2014.28015
  20. Wachter, A., Biegler, L. T. (2005). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, 106 (1), 25–57. doi: 10.1007/s10107-004-0559-y

Downloads

Published

2017-02-13

How to Cite

Komyak, V., Komyak, V., & Danilin, A. (2017). A study of ellipse packing in the high-dimensionality problems. Eastern-European Journal of Enterprise Technologies, 1(4 (85), 17–23. https://doi.org/10.15587/1729-4061.2017.91902

Issue

Vol. 1 No. 4 (85) (2017): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2017 Valentina Komyak, Vladimir Komyak, Alexander Danilin

Creative Commons License

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.