Open AccessOptimized packing multidimensional hyperspheres: a unified approach
Author(s) -
Yu. G. Stoyan,
Georgiy Yaskov,
Tatiana Romanova,
Igor Litvinchev,
Sergey V. Yakovlev,
José Manuel Velarde-Cantú
Publication year - 2020
Publication title -
mathematical biosciences and engineering
Language(s) - Uncategorized
Resource type - Journals
SCImago Journal Rank - 0.451
H-Index - 45
eISSN - 1551-0018
pISSN - 1547-1063
DOI - 10.3934/mbe.2020344
Subject(s) - mathematics , container (type theory) , mathematical optimization , nonlinear programming , packing problems , dimension (graph theory) , knapsack problem , bounded function , intersection (aeronautics) , benchmark (surveying) , nonlinear system , mathematical analysis , combinatorics , physics , mechanical engineering , geodesy , quantum mechanics , geography , engineering , aerospace engineering
In this paper an optimized multidimensional hyperspheres packing problem (HPP) is considered for a bounded container. Additional constraints, such as prohibited zones in the container or minimal allowable distances between spheres can also be taken into account. Containers bounded by hyper- (spheres, cylinders, planes) are considered. Placement constraints (non-intersection, containment and distant conditions) are formulated using the phi-function technique. A mathematical model of HPP is constructed and analyzed. In terms of the general typology for cutting & packing problems, two classes of HPP are considered: open dimension problem (ODP) and knapsack problem (KP). Various solution strategies for HPP are considered depending on: a) objective function type, b) problem dimension, c) metric characteristics of hyperspheres (congruence, radii distribution and values), d) container's shape; e) prohibited zones in the container and/or minimal allowable distances. A solution approach is proposed based on multistart strategies, nonlinear programming techniques, greedy and branch-and-bound algorithms, statistical optimization and homothetic transformations, as well as decomposition techniques. A general methodology to solve HPP is suggested. Computational results for benchmark and new instances are presented.