Packing Unequal Circles into a Minimum-Radius Circle Using r-Algorithm

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.