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 66
- Downloads 0
Influence of Lubricating-Cooling Technological Media on Metal Destruction During Cutting
The influence of lubricating and cooling technological means on the destruction of metal during cutting is shown. It has been established that the most effective additives to lubricating and cooling technological means (...
New Generation 'Block-Modular' Condenser for K-1000-60/1500-2 Turbine Units in Zaporozhskaya NPP
The condensing devices of steam turbine plants considerably determine the reliable and economical operation of NPP power units. In some cases, breakdowns in their operation result in a forced decrease in the electric cap...
Numerical Simulation of Metal Hydride Battery Heat Conducting Matrix Heat-stressed and Deformed State
The problem of safe and effective storage of hydrogen is dealt with by many researchers in different countries. The method of storing hydrogen in a chemically bound state in metal hydride accumulators has a number of adv...
Modeling Heat and Mass Exchange Processes in Metal-hydride Installations
Hydrogen as an environmentally friendly energy carrier is increasingly used in various sectors of the economy of industrialized countries, primarily to improve the environmental situation. Regardless of the field of appl...
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...