METHODOLOGICAL BASIS OF SOLVING SPHERE PACKING PROBLEM: TRANSFORMATION OF KNAPSACK PROBLEM TO OPEN DIMENSION PROBLEM

Article Sidebar

PDF
DOI: https://doi.org/10.20998/2522-9052.2019.1.09
Keywords:
sphere, hypersphere, sphere packing, knapsack problem, open dimension problem, nonlinear optimization

Main Article Content

Georgiy Yaskov
A. Pidgorny Institute of Mechanical Engineering Problems of the NAS of Ukraine, Kharkiv
https://orcid.org/0000-0002-1476-1818
Sergiy Shekhovtsov
Kharkiv National University of Internal Affairs, Kharkiv
https://orcid.org/0000-0003-2381-7999

Abstract

The subject matter of the paper is the problem of optimal packing of spheres of different dimension into a container of arbitrary geometric shape. The goal is to construct a mathematical model which associates different statements of the problem. Sphere packing problems (SPP) are combinatorial optimization problems known as cutting and packing problems. SPP consists in placement of a given set of spheres with given radii into a container of regular or irregular geometric shape. The task to be solved are: to investigate mathematical models of the two formulations according to the classification of cutting and packing problems: knapsack problems (KP) and open dimension problems (ODP); to construct a mathematical model which allow solve KP as ODP. The methods used are: the phi-function technique, increasing the problem dimension, homothetic transformations. KP is formulated as mixed discrete-continuous programming problem. A new approach which reduces solving KP to solving ODP for packing unequal and equal spheres into a container with the variable coefficient of homothety and allows adopt the jump algorithm for KP is suggested. To this end, for a given set of spheres KP is stated as a nonlinear programming problem in which the coefficient of homothety is an independent variable bounded below. The unit value of the coefficient corresponds to the original size of the container. A graphical illustration of the optimization process is presented. Conclusions. The approach suggested is a methodological basis for solving SPP. The generality of the approach lies in the fact that solving SPP does not depend on its formulation (KP or ODP). The approach is suitable for packing unequal and equal spheres into containers of arbitrary spatial shapes for which phi-functions can be constructed.

Article Details

How to Cite
Yaskov, G., & Shekhovtsov, S. (2019). METHODOLOGICAL BASIS OF SOLVING SPHERE PACKING PROBLEM: TRANSFORMATION OF KNAPSACK PROBLEM TO OPEN DIMENSION PROBLEM. Advanced Information Systems, 3(1), 54–57. https://doi.org/10.20998/2522-9052.2019.1.09
Issue
Vol. 3 No. 1 (2019): Advanced Information Systems
Section
Methods of information systems synthesis
Author Biographies

Georgiy Yaskov, A. Pidgorny Institute of Mechanical Engineering Problems of the NAS of Ukraine, Kharkiv

Candidate of Technical Sciences, Associate Professor, Senior Researcher

Sergiy Shekhovtsov, Kharkiv National University of Internal Affairs, Kharkiv

Candidate of Technical Sciences, Associate Professor, Professor of the Department

References

Hifi, M. and M'Hallah, R. (2009), “A literature review on circle and sphere packing problems: models and methodologies”, Advances in Operations Research, Vol. 2009, available at: http://downloads.hindawi.com/journals/aor/2009/150624.pdf DOI: https://doi.org/10.1155/2009/150624

Leary, M., Merli, L., Torti, F., Mazur, M. and Brandt, M. (2014), “Optimal topology for additive manufacture: A method for enabling additive manufacture of support-free optimal structures”, Materials and Design, Vol. 63, pp. 678–690.

Blyuss, O., Koriashkina, L., Kiseleva, E. and Molchanov, R. (2015), “Optimal Placement of Irradiation Sources in the Planning of Radiotherapy: Mathematical Models and Methods of Solving”, Computational and Mathematical Methods in Medicine, Vol. 2015, p. 8, DOI: https://doi.org/10.1155/2015/142987

Agapie, S.C. and Whitlock, P.A. (2010), “Random packing of hyperspheres and Marsaglia's parking lot test", Monte Carlo Methods and Applications, Vol. 16(3-4), pp.197–209.

Conway, J. H. and Sloane, N.J.A. (2010), Sphere Packings, Lattices, and Groups, New York, Springer-Verlag, 703 p.

Torquato, S. (2006), “Exactly solvable disordered sphere-packing model in arbitrary-dimensional Euclidean spaces”, Physical Review, vol. E 73, 031106.

Waescher, G. and Haussner, H. (2007), “An improved typology of cutting and packing problems”, European Journal of Operational Research, Vol. 183, pp. 1109–1130.

Hifi, M. and Yousef, L. (2015), “A dichotomous search-based heuristic for the three-dimensional packing problem", Cogent Engineering, Vol. 1, pp. 1–15.

Hifi, M. and Yousef, L. (2019), "A local search-based method for sphere packing problems", European Journal of Operational Research, Vol. 274, Issue 2, pp. 482-500.

Birgin, E.G. and Sobral, F.N.C. (2008), “Minimizing the object dimensions in circle and sphere packing problems” Computers & Operations Research, Vol. 35, pp. 2357–2375.

Stoyan, Yu. and Yaskov, G. (2012), "Packing congruent hyperspheres into a hypersphere", Journal of Global Optimization, Vol. 52(4), pp. 855–868.

Yakovlev, S.V., Yaskov, G.N. and Korobchinskiy, K.P. (2017), “O metodah peremennogo radiusa v zadache upakovki sharov v konteynery [About variable radius methods in problems of packing spheres into containers]”, Pytannya prikladnoyi matematyky i matematuchnogo modelyuvannya, DNU, Dnipro, Issue 17, pp. 265–272.

Stoyan, Yu.G., Scheithauer, G. and Yaskov, G.N. (2016), “Packing unequal spheres into various containers”, Cybernetics and Systems Analysis, Vol. 52(3), pp. 419–426.

Yaskov, G.N. (2014), “Packing non-equal hyperspheres into a hypersphere of minimal radius”, Problemy Mashinostroeniya, Vol. 17, No 2, pp. 48–53.

Stoyan, Yu. and Yaskov G. (2014), “Packing unequal circles into a strip of minimal length with a jump algorithm”, Optimization Letters, Vol. 8(3), pp. 949–970.

Chernov, N., Stoyan, Yu., Romanova, T. (2010), “Mathematical model and efficient algorithms for object packing problem”, Computational Geometry, Vol. 43(5), pp. 535–553.

Stoyan, Y., Pankratov, A. and Romanova, T. (2016), “Quasi-phi-functions and optimal packing of ellipses”, Journal of Global Optimization, Vol. 65(2), pp. 283–307.