Geodesic
Numerical optimization methods for packing equal orthogonally oriented ellipses in a rectangular domain
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 53 (2013) no. 11, pp. 1923-1938 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Linear models are constructed for the numerical solution of the problem of packing the maximum possible number of equal ellipses of given size in a rectangular domain $R$. It is shown that the $l_p$ metric can be used to determine the conditions under which ellipses with mutually orthogonal major axes (orthogonally oriented ellipses) do not intersect. In $R$ a grid is constructed whose nodes generate a finite set $T$ of points. It is assumed that the centers of the ellipses can be placed only at some points of $T$. The cases are considered when the major axes of all the ellipses are parallel to the $x$ or $x$ axis or the major axes of some of the ellipses are parallel to the $x$ axis and the others, to the $y$ axis. The problems of packing equal ellipses with centers in $T$ are reduced to integer linear programming problems. A heuristic algorithm based on the linear models is proposed for solving the ellipse packing problems. Numerical results are presented that demonstrate the effectiveness of this approach. 
@article{ZVMMF_2013_53_11_a12,
     author = {Sh. I. Galiev and M. S. Lisafina},
     title = {Numerical optimization methods for packing equal orthogonally oriented ellipses in a rectangular domain},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1923--1938},
     year = {2013},
     volume = {53},
     number = {11},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2013_53_11_a12/}
}
TY  - JOUR
AU  - Sh. I. Galiev
AU  - M. S. Lisafina
TI  - Numerical optimization methods for packing equal orthogonally oriented ellipses in a rectangular domain
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2013
SP  - 1923
EP  - 1938
VL  - 53
IS  - 11
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2013_53_11_a12/
LA  - ru
ID  - ZVMMF_2013_53_11_a12
ER  - 
%0 Journal Article
%A Sh. I. Galiev
%A M. S. Lisafina
%T Numerical optimization methods for packing equal orthogonally oriented ellipses in a rectangular domain
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2013
%P 1923-1938
%V 53
%N 11
%U http://geodesic.mathdoc.fr/item/ZVMMF_2013_53_11_a12/
%G ru
%F ZVMMF_2013_53_11_a12
Sh. I. Galiev; M. S. Lisafina. Numerical optimization methods for packing equal orthogonally oriented ellipses in a rectangular domain. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 53 (2013) no. 11, pp. 1923-1938. http://geodesic.mathdoc.fr/item/ZVMMF_2013_53_11_a12/

[1] Castillo I., Kampos F. J., Pinter J. D., “Solving circle packing problems by global optimization: Numerical results and industrial applications”, European J. Operatonal Research, 191 (2008), 786–802 | DOI | MR | Zbl

[2] Hifi M., M'Hallah R., “A literature review on circle and sphere packing problems: Models and methodologies”, Advances in operations research, 2009, 150624 | DOI | Zbl

[3] Locatelli M., Raber M., “Packing equal circles in a square. A deterministic global optimization approach”, Discrete Appl. Math., 122 (2008), 139–166 | DOI | MR

[4] Lodi A., Martello S., Monaci M., “Two-dimensional packing problems: A survey”, European J. Operational Research, 141 (2002), 241–252 | DOI | MR | Zbl

[5] Szabó P. G., Marcť M., Cs., Csendes T., Specht E. et al., New approaches to circle packing in a square. With program codes, Springer, 2007 | MR

[6] Hamacher H. W., Drezner Z. (eds.), Facility location: Application and theory, Springer-Verlag, New York, 2004 | MR

[7] Love R. F., Morris J. G., Wesolowsky G. O., Facilities location models and methods, ORSA publications in operational research series, North Holland, 1988 | MR | Zbl

[8] ReVelle C. S., Eiselt H. A., “Location analysis: A synthesis and survey”, European J. Operational Research, 165 (2005), 1–19 | DOI | MR | Zbl

[9] Hiragi Y., “Molecular shape and structure of regular molecular assembles. II: The geometrical conditions for two dimensional packing of the elliptic molecule”, Bull. Inst. Chem. Res. Kyoty Univ., 56:4 (1978), 170–175

[10] Xu W. X., Chen H. S., “Micro structural characterization of fresh cement paste via random packing of ellipsoidal cement particles”, Materials Characterization, 66 (2012), 16–23 | DOI

[11] Delaney G., Weaire D., Hutzler S., Murphy S., “Random packing of elliptical disks”, Philosophical Magazine Letters, 85:2 (2005), 89–96 | DOI

[12] Tóth L. F., “Packing of ellipses with continuously distributed area”, J. Discrete Mathematics, 60 (1986), 263–267 | MR | Zbl

[13] Xu W. X., Chen H. S., Lu Z., “An overlapping detection algorithm for random sequential packing of elliptical particles”, Physica A, 390 (2011), 2452–2467 | DOI

[14] Zhou Z. Y., Pinson D., Zou R. P., Yu A. B., “Discrete particle simulation of gas fluidization of ellipsoidal particles”, Chem. Eng. Sci., 65 (2011), 6128–6145 | DOI

[15] Galiev Sh. I., “Vychislitelnye algoritmy optimizatsii pokrytii ploskikh oblastei zadannym chislom ellipsov”, Zh. vychisl. matem. i matem. fiz., 35:5 (1995), 772–783 | MR | Zbl

[16] Canbolat M. S., von Massow M., “Planar maximal covering with ellipses”, Computers Industrial Engng., 57 (2009), 201–208 | DOI

[17] Galiev Sh., Lisafina M., Judin V., “Optimization of a multiple covering of a surface taking into account its relief”, Proceedings of III International conference Optimization and Applications (OPTIMA-2012) (Costa da Caparica, Portugal, September 2012), M., 2012, 86–90