2024, issue 4, p. 5-21
Received 05.09.2024; Revised 29.09.2024; Accepted 03.12.2024
Published 18.12.2024; First Online 23.12.2024
https://doi.org/10.34229/2707-451X.24.4.1
Previous | FULL TEXT (in Ukrainian) | Next
Packing Unequal Circles into a Minimum-Radius Circle Using r-Algorithm
Bohdan Zadorozhnyi 1 *,
Tetyana Romanova 2 
, Petro Stetsyuk 1,
3 , Stanislav Tyvodar 1,
Sergiy Shekhovtsov 4
1 Uzhhorod National University,
2 University of Leeds, UK
3 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
4 Kharkiv National University of Radioelectronics
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Two approaches to employ the Shor’s r-algorithm for solving a problem of packing unequal circles into a minimum-radius circle are studied.
The first approach uses multistart of the r-algorithm with a step dichotomy from a set of feasible starting points. Each feasible point is taken as the best solution found by a heuristic algorithm. Two versions of the algorithm are considered. For the first version, the step value is halved during the iteration process. The second version provides an option that allows to restore the maximum value of the r-algorithm step value. The algorithm is implemented using Rust 1.70.0 programming language and nalgebra 0.32.3 library. Both versions of the algorithm are tested for 50 test problems of the international competition “Dense packing of circles in a circle of minimum radius” to improve the results found by the heuristic. In most cases, the second version showed better solutions.
The second approach employs the r-algorithm with an adaptive step to find the best local minimum of a multiextremal nonsmooth function using multistart strategy from a set of randomly chosen starting points. It is implemented using Julia programming language and uses large numbers (128 and 256 bits). Computational experiments are tested for a benchmark problem with five circles. These results are compared to the problem solutions provided on the website http://www.packomania.com/. It is shown that increasing the bit depth leads to decreasing the number of the r-algorithm iterations while increasing the accuracy of the objective function value. With correctly chosen parameters, the r-algorithm finds all 28 digits after the decimal point, which are presented on the website http://www.packomania.com/.
Keywords: circle packing, r-algorithm, heuristic algorithm, Rust, Julia.
Cite as: Zadorozhnyi B., Romanova T., Stetsyuk P., Tyvodar S., Shekhovtsov S. Packing Unequal Circles into a Minimum-Radius Circle Using r-Algorithm. Cybernetics and Computer Technologies. 2024. 4. P. 5–21. (in Ukrainian) https://doi.org/10.34229/2707-451X.24.4.1
References
1. Zadorozhnyi B., Mitsa O., Stetsyuk P. On the Improvement of the Heuristic Algorithm for Packing Circles into a Circle of Minimum Radius. Cybernetics and Computer Technologies. 2023. 2. P. 32–45. https://doi.org/10.34229/2707-451X.23.2.4
2. Zadorozhnyi B.O., Romanova T.Y., Stetsyuk P.I. Improving on heuristic algorithm of unequal circles packing using Shor’s r-algorithm. Proceedings of XXVI International scientific and practical seminar “Combinatorial configurations and their applications” (Kropyvnytskyi – Zaporizhzhia – Kyiv, June 13-15, 2024). Kropyvnytskyi: PC “EkskluzyvSystem”, 2024. P. 59–65.
3. Shor N.Z. Minimization Methods for Nondifferentiable Functions and Their Applications. Kyiv: Naukova dumka, 1979. 200 p.
4. Shor N.Z. Non-Differentiable Optimization and Polуnomial Problems. Kluwer Academic Publishers, Boston, Dordrecht, London. 1998. 412 p.
5. Stetsyuk P.I., Romanova T.Y., Tyvodar S.R. Using of BARON solver for solving quadratic problem of optimal packing of unequal circles. Proceedings of XXVI International scientific and practical seminar “Combinatorial configurations and their applications” (Kropyvnytskyi – Zaporizhzhia – Kyiv, June 13-15, 2024). Kropyvnytskyi: PC “EkskluzyvSystem”, 2024. P. 179–188.
6. Tawarmalani M., Sahinidis N.V. A polyhedral branch-and-cut approach to global optimization. Mathematical Programming. 2005. 103 (2). P. 225–249. https://doi.org/10.1007/s10107-005-0581-8
7. Sahinidis N.V. BARON 21.1.13: Global Optimization of Mixed-Integer Nonlinear Programs, User's manual, 2021.
8. Dense packing of circles into a circle of minimal radius. Eolymp. https://packing-circles.eolymp.io (accessed: 23.05.2024)
9. Stetsyuk P.I. Theory and software of Shor’s r-algorithms. Cybernetics and systems analysis. 2017. Vol. 53. P. 692–703. https://doi.org/10.1007/s10559-017-9971-1
10. Stetsyuk P.I. Subgradient methods ralgb5 and ralgb4 for minimization of ravine convex functions. Vychislitelnye tehnologii. 2017. Vol. 22, No. 2. P. 127–149.
11. Stetsyuk P.I. Computer program “Octave-program ralgb5a: r(α)-algorithm with adaptive step”. Certificate of copyright registration for the work № 85010. Ukraine. Ministry of Economic Development and Marketing. State Department of Intellectual Property. Registration date 29.01.2019.
12. Packomania. http://www.packomania.com/ (accessed: 09.08.2023)
13. Romanova T., Pankratov A., Litvinchev I., Stetsyuk P., Lykhovyd O., Marmolejo-Saucedo J.A., Vasant P. Balanced Circular Packing Problems with Distance Constraints. Computation. 2022. 10 (7). 113. https://doi.org/10.3390/computation10070113
14. Romanova T.E., Stetsyuk P.I., Chugay A.M., Shekhovtsov S.B. Parallel Computing Technologies for Solving Optimization Problems of Geometric Design. Cybernetics and Systems Analysis. 2019. 55 (6). P. 894–904. htps://doi.org/10.1007/s10559-019-00199-4
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next