Solving the problem of optimal packing of homothetic ellipsoids into a container of minimal volume
Keywords:
optimal packing, homothetic ellipsoids, phi-functions, starting point, non-overlapping, containment, nonlinear optimization, iterative procedure, LOFRT procedureAbstract
The paper studies the packing problem of homothetic the same oriented ellipsoids into a container of minimal volume. The container can be a rectangular parallelepiped or an ellipsoid. We formulate the model in the form of a nonlinear programming problem. To constract the non-overlapping and containment constraints using of phi-function technique. We propose the efficient algorithm, which employes a homothetic transformation of ellipsoids and the optimization procedure Local Optimization with Feasible Region Transformation (LOFRT), which allow us to reduce considerably the dimension of the problem and computational time. Our algorithm also involves generating a number of random starting points. We choose the best local minimum as the solution of the problem. Our model can be realized by the current state-of-the art local or global solvers. A several computational results are providedReferences
1. Wright S. J. Packing Ellipsoids with Overlap. SIAM Review, 55(4):671-706. 2013.
2. Kallrath J. Packing ellipsoids into volume-minimizing rectangular boxes. Journal of Global Optimization. DOI:10.1007/s10898-015-0348-6.
3. Pankratov A., Romanova T., Khlud O. Quasi-phi-functions in packing of ellipsoids. Radioelectronics & Informatics, 68:37–42. 2015.
4. Lubachevsky B. D., Stillinger F. H. Geometric properties of random disk packings. Journal of Statistical Physics, 60 (5–6):561-583. 1990.
5. Bennell J. A., Oliveira J. F. A tutorial in irregular shape packing problem.Journal of the Operational Research Society. 2009. 60:93–105.
6. Chernov N., Stoyan Yu., Romanova T. Mathematical model and efficient algorithms for object packing problem. Computational Geometry: Theory and Applications. 2010. Vol. 43, № 5. P. 533-553.
7. Stetsuk P. I., Romanova T. E., Subota I. O. NLP-zadacha upakovky homotetychnyh elipsiv u priamokutnyi konteiner. Teoriya optymalnyh rishen: zb. nauk. pr. – Kiev: In. kibernetyky im. V. M. Hkushkova NAN Ukrainy. 2014. S. 139-146.
8. 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 Operational Research. 2004. Vol. 156. P. 590–600.
9. Stoyan Y., Pankratov A., Romanova T. Quasi-phi-functions and optimal packing of ellipses. Journal of Global Optimization. 2015. DOI:10.1007/s10898-015-0331-2.
Downloads
Published
Issue
Section
License
Copyright (c) 2016 О. М. Хлуд
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.
All authors agree with the following conditions:
- The authors reserve the right to claim authorship of their work and transfer to the journal the right of first publication of the work under the license agreement (the agreement).
- Authors have a right to conclude independently additional agreement on non-exclusive spreading the work in the form in which it was published by the jpurnal (for example, to place the work in institution repository or to publish as a part of a monograph), providing a link to the first publication of the work in this journal.
- Journal policy allows authors to place the manuscript in the Internet (for example, in the institution repository or on a personal web sites) both before its submission to the editorial board and during its editorial processing, as this ensures the productive scientific discussion and impact positively on the efficiency and dynamics of citation of published work (see The Effect of Open Access).
