Numerical methods for constructing suboptimal~packings of~nonconvex domains with~curved~boundary

P. D. Lebedev ; V. N. Ushakov ; A. A. Uspenskii

Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 4, pp. 58-79.

Résumé

We study the problem of constructing some optimal packings of simply-connected nonconvex plane domains with a union of congruent circles. We consider the minimization of the radius of circles if the number of the circles is fixed. Using subdifferential calculus, we develop theoretical methods for solution of the problem and propose an approach for constructing some suboptimal packings close to optimal. In the numerical algorithms, we use the iterative procedures and take into account mainly the location of the current center of a packing element, the centers of the nearest neighboring elements, and the points of the boundary of the domain. The algorithms use the same supergradient ascent scheme whose parameters can be adapted to the number of packing elements and the geometry of the domain. We present a new software package whose efficiency is demonstrated by several examples of numerical construction of some suboptimal packings of the nonconvex domains bounded by the Cassini oval, a hypotrochoid, and a cardioid. Illustr. 6, bibliogr. 37.

Détail

Keywords: packing, maximization, optimization, algorithm, numerical procedure, directional derivative, superdifferential, approximation, supergradient ascent.

Bibliographie

[1] N. N. Krasovskii, A. I. Subbotin, Positional Differential Games, Nauka, M., 1974 (Russian) | MR

[2] V. N. Ushakov, A. A. Uspenskii, A. G. Malev, “An estimate of the stability defect for a positional absorption set subjected to discriminant transformations”, Proc. Steklov Inst. Math., 279, Suppl. (2012), 113–129 | DOI

[3] V. N. Ushakov, P. D. Lebedev, N. G. Lavrov, “Algorithms for optimal packings in ellipse”, Vestn. Yuzhno-Ural. Gos. Univ., Ser. Mat. Model. Program., 10:3 (2017), 67–79 (Russian) | Zbl

[4] P. D. Lebedev, A. L. Kazakov, “Iterative methods for the construction of planar packings of circles of different size”, Tr. Inst. Mat. Mekh., 24, no. 2, 2018, 141–151 (Russian)

[5] J. Machchhar, G. Elber, “Dense packing of congruent circles in free-form nonconvex containers”, Comput. Aided Geom. Des., 52-53 (2017), 13–27 | DOI | MR | Zbl

[6] L. Meng, C. Wang, X. Yao, “Non-convex shape effects on the dense random packing properties of assembled rods”, Physica A, 490 (2017), 212–221 | DOI | MR

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

[8] Y. Li, H. Akeb, Basic heuristics for packing a large number of equal circles, Univ. Picardie Jules Verne, Amiens, 2005, 19 pp. (accessed Aug. 13, 2020) www.researchgate.net/publication/250761942_Basic_Heuristics_for_Packing_a_Great_Number_of_Equal_Circles

[9] I. Litvinchev, L. Ozuna, “Approximate packing circles in a rectangular container: Valid inequalities and nesting”, J. Appl. Res. Technology, 12:4 (2014), 716–723 | DOI | MR

[10] Yu. G. Stoyan, G. Yas'kov, “A mathematical model and a solution method for the problem of placing various-sized circles into a strip”, Eur. J. Oper. Res., 156 (2004), 590–600 | DOI | MR | Zbl

[11] Yu. G. Stoyan, G. Yas'kov, “Packing identical spheres into a rectangular parallelepiped”, Intelligent Decision Support: Current Challenges and Approaches, Gabler-Verl., Wiesbaden, 2008, 46–67

[12] M. Hifi, R. M'Hallah, “Approximate algorithms for constrained circular cutting problems”, Comput. Oper. Res., 31 (2004), 675–694 | DOI

[13] A. M. Chugai, “A solution to the disk packing problem in a convex polygon with the use of a modified method of tapering neighborhoods”, Radioélektron. Inform., 2005, no. 1, 58–63 (Russian)

[14] P. D. Lebedev, A. A. Uspenskii, “Construction of the optimal result function and dispersing lines in time-optimal problems with a nonconvex target set”, Tr. Inst. Mat. Mekh., 22, no. 2, 2016, 188–198 (Russian)

[15] A. L. Kazakov, A. A. Lempert, T. T. Ta, “The sphere packing problem into bounded containers in three-dimension non-Euclidean space”, IFAC-PapersOnLine, 51:32 (2018), 782–787 | DOI

[16] A. L. Kazakov, A. A. Lempert, H. L. Nguyen, “An algorithm of packing congruent circles in a multiply connected set with non-Euclidean metrics”, Vychisl. Metody Program., 17:2 (2016), 177–188 (Russian)

[17] A. L. Kazakov, A. A. Lempert, H. L. Nguyen, “The problem of the optimal packing of the equal circles for special non-Euclidean metric”, Commun. Comput. Inf. Sci., 661 (2017), 58–68

[18] P. D. Lebedev, A. A. Uspenskii, “Algorithms of optimal packing construction in a 3-dimensional Euclidian space”, Modern Problems in Mathematics and Its Applications, Proc. 47th Int. Youth School-Conf. MPMA 2016 (Yekaterinburg, Russia, Jan. 31–Feb. 6, 2016), CEUR Workshop Proc., 1662, RWTH Aachen Univ., Aachen, 84–93 (accessed Aug. 13, 2020) www.ceur-ws.org/Vol-1662

[19] A. I. Subbotin, Generalized Solutions of First-Order PDEs: The Dynamical Optimization Perspective, Birkhäuser, Boston, 1995

[20] V. F. Demyanov, L. V. Vasilyev, Non-Differentiable Optimization, Nauka, M., 1981 (Russian) | MR

[21] I. V. Bychkov, A. L. Kazakov, A. A. Lempert, D. S. Bukharov, A. B. Stolbov, “An intelligent management system for the development of a regional transport logistics infrastructure”, Autom. Remote Control, 77:2 (2016), 332–343 | DOI | MR | Zbl

[22] V. L. Rvachov, Yu. G. Stoyan, “The problem of optimal placement of circular ingots”, Kibernetika, 1965, no. 3, 77–83 (Russian)

[23] I. Castillo, F. J. Kampas, J. D. Pinter, “Solving circle packing problems by global optimization: Numerical results and industrial applications”, Eur. J. Oper. Res., 191:3 (2008), 786–802 | DOI | MR | Zbl

[24] F. Harary, W. Randolph, P. G. Mezey, “A study of maximum unit-circle caterpillars tools for the study of the shape of adsorption patterns”, Discrete Appl. Math., 67:1–3 (1996), 127–135 | DOI | MR | Zbl

[25] A. V. Eremeev, L. A. Zaozerskaya, A. A. Kolokolov, “The set covering problem: Complexity, algorithms, and experimental investigations”, Diskretn. Anal. Issled. Oper., Ser. 2, 7:2 (2000), 22–46 (Russian) | MR

[26] R. Rockafellar, Convex Analysis, Princeton Univ., Princeton, 1970 | MR | Zbl

[27] P. D. Lebedev, A. V. Ushakov, “Approximating sets on a plane with optimal sets of circles”, Autom. Remote Control, 73:3 (2012), 485–493 | DOI | MR | Zbl

[28] A. G. Sukharev, A. V. Timokhov, V. V. Fyodorov, A Course in Optimization Methods, Nauka, M., 1986 (Russian) | MR

[29] E A. Nurminskii, D. Tien, “Method of conjugate subgradients with constrained memory”, Autom. Remote Control, 75:4 (2012), 646–656 | DOI | MR | Zbl

[30] E. A. Vorontsova, “Linear tolerance problem for input-output model with interval data”, Vychisl. Tekhnol., 22:2 (2017), 67–84 (Russian) | Zbl

[31] A. V. Gasnikov, P. E. Dvurechenskii, D. I. Kamzolov, Yu. E. Nesterov, V. G. Spokoiny, P. I. Stetsyuk, A. L. Suvorikova, A. V. Chernov, “Searching for equilibriums in multistage transport models”, Tr. Mosk. Fiz. Tekh. Inst., 7:4 (2015), 143–155 (Russian)

[32] P. D. Lebedev, A program for calculating the optimal coverage of a hemisphere with a set of spherical segments, Certificate of State Registration No 2015661543 from 29.10.2015 (Russian)

[33] L. F. Tóth, Lagerungen in der Ebene, auf der Kugel und im Raum, Grundlehren Math. Wiss., 65, Springer, Heidelberg, 1953 (German) | MR

[34] L. M. Mestetskii, Continuous Morphology of Binary Images: Figures, Skeletons, Circulars, FIZMATLIT, M., 2009 (Russian)

[35] P. D. Lebedev, A. A. Uspenskii, “Construction of a nonsmooth solution to the time-optimal problem with a low order of smoothness of the target set boundary”, Tr. Inst. Mat. Mekh., 25, no. 1, 2019, 108–119 (Russian)

[36] A. A. Savyolov, Flat Curves: Systematics, Properties, Applications, Librokom, M., 2010 (Russian)

[37] E. Specht, Packomania, , 2018 (accessed Aug. 13, 2020) www.packomania.com | Zbl