Optimized packing multidimensional hyperspheres: a unified approach
| Autor: | José Manuel Velarde Cantú, Igor Litvinchev, Sergey Yakovlev, Georgiy Yaskov, Yuriy Stoyan, Tatiana E. Romanova |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Mathematical optimization
knapsack problem Container (type theory) Nonlinear programming Homothetic transformation phi-function QA1-939 Mathematics Applied Mathematics open dimension problem mathematical modeling General Medicine Hypersphere hypersphere Computational Mathematics Packing problems Knapsack problem Modeling and Simulation Bounded function Metric (mathematics) packing General Agricultural and Biological Sciences optimization TP248.13-248.65 Biotechnology |
| Zdroj: | Mathematical Biosciences and Engineering, Vol 17, Iss 6, Pp 6601-6630 (2020) |
| ISSN: | 1551-0018 |
| DOI: | 10.3934/mbe.2020344?viewType=HTML |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|