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 78
- Downloads 0
Roller Forming Unit Dynamic Analysis with Energy Balanced Drive Dissipative Properties Taken into Account
In order to increase the reliability and durability of a roller forming unit with an energy-balanced drive, loads in the unit structure elements and drive are calculated, dependencies for identifying efforts in the conne...
Use of Computer Technology in Modernization of Head Covers for ПЛ 20-В-500 Kaplan Turbines
<p class="a">One of the problems faced by a designer in the modernization of operating generating units is the analysis of the feasibility of ensuring the strength and reliability of turbine parts and components in their...
Packing convex homothetic polytopes into a cuboid
This paper deals with the optimization problem of packing a given set of homothetical arbitrarily oriented convex polytopes without their overlapping in a linear parallelepiped of minimal volume. Phi-functions are propos...
Chaotic Oscillations of a Kinematically Excited Flat Shell During Geometrically Non-linear Deformation
We study the forced oscillations of a cantilevered flat shell of constant curvature. These movements are excited by a kinematic periodic embedding motion. To describe geometrically non-linear deformation, the non-linear...
Stepwise Optimization of I-section Flexible Elements Under a Fuzzy Approach to Taking into Account Corrosion and Protective Properties of Anticorrosive Coating
This paper is a continuation of research in the field of optimal design of structures under a combined approach to the measurement of corrosion and anticorrosion protective properties of coatings. As noted earlier, such...