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 74
- Downloads 0
Re-Extension of 200 MW Turbine Cast Casing Service
To date, the fleet service life of a significant number of DTEK Energy power units is ex-ceeded. In particular, this relates to the structural components of the K-200-130-3 steam turbine of the power unit No. 9 of DTEK L...
Design Forecasting of Thermal Strength and Resource of Steam Turbine structural Components
Effective and reliable operation of power units is closely connected with the provision of the thermal strength and durability of their elements and components. The needs of the modern energy market lead to the operation...
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...
Modernization of an experimental installation and a procedure for investigating the anisotropic viscoelastic properties of composite materials at elevated temperatures
The paper describes the process of modernizing the existing installation designed for performing long-term tests of steel and aluminum cylindrical specimens for high-temperature creep with the purpose of conducting the e...
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...