Methodology to Solve Multi-Dimentional Sphere Packing Problems
Journal Title: Проблеми машинобудування - Year 2019, Vol 22, Issue 1
Abstract
This paper discusses the problem of optimally packing spheres of various dimensions into containers of arbitrary geometrical shapes. According to the international classification, this problem belongs to Sphere Packing Problems (SPPs). The problem is to pack a set of spheres (circles, hyperspheres) with given radii into a container with given metric characteristics. The aim of this work is to create an integrated methodology for solving SPPs. The basic formulations of the problem are presented: in the form of the knapsack problem (KP), open dimension problem (ODP), and their corresponding mathematical models. The solution strategy selection is influenced by the form of problem statement, dimension of the space where the spheres are to be packed, metric peculiarities of the spheres (equal or unequal), number of the spheres to be packed, geometric shape of the container, presence of technological restraints, and count time limit. The structural elements of the methodology are mathematical models, methods for constructing initial packings, and methods of local and global optimization. In developing the solution method, we construct the initial feasible packings by using both the random and lattice methods, using a greedy algorithm and solving an auxiliary nonlinear programming problem. As local optimization methods, we consider the modifications of the feasible direction method, interior point method, Lagrange multiplier method, and method of optimization in groups of variables. For global optimization, we use the method of enumerating the subsets of spheres of a given set and method of enumerating the extreme points of the feasible region, which are implemented by using the branch and bound algorithm, the modifications of the decremental neighborhood search method, method of smooth transition from one local minimum to another by increasing problem dimensionality and introducing additional variable metric characteristics, solution method implemented as a sequence of non-linear programming problems of increasing dimensionality, and a multi-start method. Strategies for solving different SPP statements are proposed.
Authors and Affiliations
Georgiy N. Yaskov
Keywords
Related Articles
- EP ID EP622746
- DOI 10.15407/pmach2019.01.067
- Views 64
- Downloads 0
Influence of the Location of a Convector on the Distribution of the Room Temperature
This article considers the influence of various options of placing heaters in a room on energy efficiency, and creating a comfortable temperature field for people to stay in. For the research, a square room with an incli...
Substantiation of Boundary Accelerations of Roller Forming Unit Optimal Reversal Mode According to Fourth-Order Acceleration
In order to increase the reliability and durability of a roller forming unit, we calculated a combined mode of the reciprocating movement of a forming trolley with the reversal according to the fourth-order acceleration...
Screw-Type Symmetry in Machine Components and Design at Implementation on a 3D Printer
The creation of mathematical models for the implementation of 3D printing is of considerable interest, which is associated with the active introduction of 3D printing in various industries. The advantages of using 3D pri...
Higher order numerical method for aeroelastic problems
The accuracy of determining the conditions for the possible onset of uncontrolled oscillations of turbine blades depends on the accuracy and detail of the aerodynamic problem solution. An increased accuracy of the simula...
Stressed State of a Hollow Cylinder with a System of Cracks under Longitudinal Shear Harmonic Oscillations
This paper solves the problem of determining the stress state near cracks in an infinite hollow cylinder of arbitrary cross section during longitudinal shear oscillations. We propose an approach that allows us to separat...