PACKING HOMOTHETIC SPHEROIDS INTO A LARGER SPHEROID WITH THE JUMP ALGORITHM
Keywords:
packing, sphere, spheroid, optimization, jump algorithmAbstract
The article considers a mathematical model of the optimization problem of packing homotethic spheroids (spheres - in particular case) into a larger spheroid (sphere - in particular case). Sphere radii are supposed to be variable. A new algorithm to derive starting points belonging to the feasible region of the problem is offered. According to the jump algorithm solving the problem is reduced to solving a sequence of mathematical programming problems yielding objective improvements. A solution strategy consisting of four stages is proposed. The first stage involves formation of starting points and computation of local minima. The second stage fulfills continuous transition from one local minimum to another. The third stage realizes reduction of the solution space dimension. The fourth stage rearranges sphere pairs to refine the objective. We provide a number of numerical results both for spheres and spheroids.
Downloads
References
Wang, J. Packing of unequal spheres and automated radiosurgical treatment planning / J. Wang // Journal of Combinatorial Optimization. – 1999. – Vol.3. – P. 453–463.
Chen, D.Z. Algorithms for congruent sphere packing and applications / D.Z. Chen , X. Hu, Y. Huang,, Y. Li, J. Xu // Proc. of Sym. on Comp. Geometry'2001. – 2001. – P. 212–221.
Sutou, A. Global optimization approach to unequal sphere packing problems in 3D / A. Sutou, Y. Day // Journal of Op t. Theory and Appl. – 2002. – Vol. 114(3). – P. 671–694.
Uhler, C. Packing Spheroids with Overlap / C. Uhler, S.J. Wright // SIAM Rev. – 2013. – Vol. 55(4). – P. 671–706.
Stoyan, Yu. Packing of Various Solid Spheres into a Parallelepiped / Yu. Stoyan, G.Yaskov, G. Scheithauer // Central European Journal of Operational Research. – 2003. – Vol. 11(4). – P. 389–407.
Zeng, Z.Z. An algorithm to packing unequal spheres in a larger sphere / Z.Z. Zeng, W.Q. Huang, R.C. Xu // Advanced Mat. Research. – 2012. – Vol. 546-547. – P. 1464-1469.
Stoyan, Yu. Packing unequal circles into a strip of minimal length with a jump algorithm / Yu. Stoyan, G. Yaskov // Optimization letters. – 2014. –Vol. 8. – P. 949–970.
Stoyan, Yu.G. Packing identical spheres into a cylinder / Yu.G. Stoyan, G.N. Yaskov // Int. Transactions in Operational Research. – 2010. – Vol. 17(1). – P. 51–70.
Stoyan, Yu.G. A mathematical model and a solution method for the problem of placing various-sized circles into a strip / Yu.G. Stoyan, G.N. Yaskov // European Journal of Op erational Research. – 2004. – Vol. 156. – P. 590–600.
Wächter, A. On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming / A. Wächter, L.T. Biegler // Mathematical Programming. – 2006. – Vol. 106(1). – P. 25–57.
Zoutendijk, G. Methods of feasible directions. A study in linear and non-linear programming / G. Zoutendijk. Amsterdam-London-New York-Princeton: Elsevier Publishing Company. – 1960. – 126 p.
