Control Systems and Computers

DOI: https://doi.org/10.15407/usim.2016.05.003

Upr. sist. maš., 2016, Issue 5 (265), pp. 3-9.

UDC 519.6

A.N. Danilin , adjunct, National University of Civil Protection of Ukraine (Kharkiv)

V.V. Komyak, PhD (Eng.), National University of Civil Protection of Ukraine (Kharkiv), E-mail: vlad1m1r@list.ru,

V.M. Komyak, Doctor (Eng.), National University of Civil Protection of Ukraine (Kharkiv), E-mail: vkomyak@ukr.net, 

A.V. Pankratov,  Doctor (Eng.), Institute of Mechanical Engineering of A.M. Podgorny NAS Ukraine (Kharkiv), E-mail: impankratov@mail.ru

The Ellipses Packing in a Rectangle of the
Minimal Size

Introduction. In this paper, we deal with the optimal ellipse packing problem, which is a part of operational research and computational geometry. Ellipse packing problems have a variety of real world applications. However, the problem has received relatively little attention in the literature so far. Finding high quality ellipse packings is a difficult computational problem.

Methods and results. The problem is formulated as follows: the set of ellipses is to be placed without overlapping, free of any orientation restrictions, on a rectangular plate such that the area of the rectangle is minimized.

The ellipses are described by the coordinates of their center and an orientation angle to allow their rotation. Two types of constraints are necessary to be modeled: the non-overlapping ellipses and the bounds placing the ellipses inside the rectangle.

A new quasi-phi-function is developed for an analytical description of non-overlapping ellipses. An additional variable is introduced for each quasi-phi-function. Already known phi-function is applied to hold the containment constraint.  

A new mathematical programming formulations for this problem in the form of a nonlinear programming problem are presented. The constrained optimization problem is NP-hard nonlinear programming problem. The solution space Q has a complicated structure. A matrix of the inequality system which specifies Q is strongly sparse and has a block structure. Our LOFRT procedure allows us to reduce the problem with O(n2) inequalities and O(n2)-dimensional solution space to a sequence of sub-problems, each with O(n)inequalities and a O(n)-dimensional solution subspace. This reduction is of a paramount importance, since it deals with non-linear optimization problems.

Conclusion. The ellipse packing problem in the form of a nonlinear programming problem is formulated and an efficient solution algorithm is developed. The presented algorithm allows to reduce the computational cost of the researched problem.

 Download full text! (In Russian)

Keywords: packaging, ellipses, continuous turns, quasi-phi-function, mathematical model, nonlinear optimization.

REFERENCE

1. Toth, L.F., 1986.Packing of ellipses with continuously distributed area. J. of Discrete Mathematics, 60, pp. 263–267. doi:10.1016/0012-365X(86)90018-X.
   https://doi.org/10.1016/0012-365X(86)90018-X
2. J.M. Ting, M. Khwaja, L.R. Meachum et al., 1993. An ellipse-based discrete element model for granular materials. Numerical and Analytical Methods in Geomechanics, 17 (9), pp. 603–623. doi:10.1002/nag. 1610170902.
3. Feng, Y., Han, K., Owen, D., 200. An Advancing Front Packing of Polygons, Ellipses and Spheres. Discrete Element Methods, pp. 93–98. doi:10.1061/40647(259)17.
   https://doi.org/10.1061/40647(259)17
4. Vickers, G.T., 2009. Nested Ellipses. Appl. Probab. Trust., 41 (3), pp. 131–137.
5. Xu, W.X., Chen, H.S., Lv, Z., 2011. An overlapping detection algorithm for random sequential packing of elliptical particles. Physica, 390, pp. 2452–2467. doi:10.1016/j.physa.2011.02.048.
   https://doi.org/10.1016/j.physa.2011.02.048
6. Kallrath, J., Rebennack, S., 2013. Cutting Ellipses from Area-Minimizing Rectangles. J. of Global Optimization, 59 (2–3), pp. 405–437. doi:10.1007/s10898-013-0125-3.
   https://doi.org/10.1007/s10898-013-0125-3
7. Kallrath, J., 2008. Cutting Circles and Polygons from Area-Minimizing Rectangles. J. of Global Optimization, 43 (2–3), pp. 299–328. doi:10.1007/s10898-007-9274-6.
   https://doi.org/10.1007/s10898-007-9274-6
8. Pankratov, A.V., Romanova, T.E., Subbota, I.A., 2014. Optimum packing of ellipses taking into account allowable distances. Journal of Computational Mathematics, T. 1, pp. 27-42.
9. Stoyan, Yu., Pankratov, A., Romanova, T., 2015. Quasi-phi-functions and optimal packing of ellipses. J. of Glob. Optim., pp. 283–307. DOI: 10.1007/s10898-015-0331-2.
   https://doi.org/10.1007/s10898-015-0331-2
10. Yu.G. Stoyan, A.V. Pankratov, T.E. Romanova et. al., 2014.Quasi-phi-functions for mathematical modeling of geometric relations. Nat. acad. Sciences of Ukraine, T. 9, pp. 49-54.
11. Yu. Stoyan, T. Romanova, A. Pankratov et al., 2015. Optimized Object Packings Using Quasi-Phi-Functions. Vol. 105 of the series Springer Optimization and Its Applications, pp. 265–293.
    https://doi.org/10.1007/978-3-319-18899-7_13
12. Birgin, E.G., Lobato, R., Martinez, J.M., 2016. Packing Ellipsoids by Nonlinear Optimization. J. of Global Optim., 65, pp. 709–743.
    https://doi.org/10.1007/s10898-015-0395-z
13. E.G. Birgin, L.H. Bustamante, H.F. Callisaya et al., 2013. Packing circles within ellipses. Int. transactions in operational res., 20 (3), pp. 365–389. doi:10.1111/ itor.12006.
14. Birgin, E.G., Martinez, J.M., 2014. Practical Augmented Lagrangian Methods for Constrained Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA.
    https://doi.org/10.1137/1.9781611973365
15. Frank J. Kampas, János D. Pintér, Ignacio Castillo et al., 2016. General Ellipse Packings in an Optimized Circle Using Embedded Lagrange Multipliers (Submitted for publication January 2016). Global Optimization Submissions, http://www.optimization-online.org/ DB_FILE/2016/01/5293.pdf.
16. Kampas, Frank J., Castillo, Ignacio, Pintér, János D., 2016. General Ellipse Packings in Optimized Regular Polygons, (Submitted for publication Feb. 2016). Global Optimization Submissions. 2016. http://www.optimization-online.org/DB_FILE/ 2016/03/5348.pdf.
17. Wachter, A., Biegler, L.T., 2006. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, 106 (1), pp. 25–57, doi:10.1007/s10107-004-0559-y.
    https://doi.org/10.1007/s10107-004-0559-y
18. A.N. Danilin, V.V. Komyak, V.M. Komyak et al., 2016. Mathematical model of individual-flow movement of human and transport flows. Vestn. Kherson. nat. tech. University. Kherson: KhNTU, 3 (58), pp. 501-505.

Received  06.09.2016