IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v11y2023i9p2033-d1132385.html
   My bibliography  Save this article

Quasi-Packing Different Spheres with Ratio Conditions in a Spherical Container

Author

Listed:
  • Andreas Fischer

    (Institute of Numerical Mathematics, Technische Universität Dresden, 01062 Dresden, Germany)

  • Igor Litvinchev

    (Graduate Program in Systems Engineering, Nuevo Leon State University (UANL), Av. Universidad s/n, Col. Ciudad Universitaria, San Nicolas de los Garza CP 66455, Nuevo Leon, Mexico)

  • Tetyana Romanova

    (A. Pidhornyi Institute of Mechanical Engineering Problems of the National Academy of Sciences of Ukraine, Pozhars’koho St., 2/10, 61046 Kharkiv, Ukraine
    Department of Systems Engineering, Kharkiv National University of Radioelectronics, 14 Nauky Ave., 61166 Kharkiv, Ukraine)

  • Petro Stetsyuk

    (V. M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, 03187 Kyiv, Ukraine)

  • Georgiy Yaskov

    (A. Pidhornyi Institute of Mechanical Engineering Problems of the National Academy of Sciences of Ukraine, Pozhars’koho St., 2/10, 61046 Kharkiv, Ukraine)

Abstract

This paper considers the optimized packing of different spheres into a given spherical container under non-standard placement conditions. A sphere is considered placed in the container if at least a certain part of the sphere is in the container. Spheres are allowed to overlap with each other according to predefined parameters. Ratio conditions are introduced to establish correspondence between the number of packed spheres of different radii. The packing aims to maximize the total number of packed spheres subject to ratio, partial overlapping and quasi-containment conditions. A nonlinear mixed-integer optimization model is proposed for this ratio quasi-packing problem. A heuristic algorithm is developed that reduces the original problem to a sequence of continuous open dimension problems for quasi-packing scaled spheres. Computational results for finding global solutions for small instances and good feasible solutions for large instances are provided.

Suggested Citation

  • Andreas Fischer & Igor Litvinchev & Tetyana Romanova & Petro Stetsyuk & Georgiy Yaskov, 2023. "Quasi-Packing Different Spheres with Ratio Conditions in a Spherical Container," Mathematics, MDPI, vol. 11(9), pages 1-19, April.
    • Handle: RePEc:gam:jmathe:v:11:y:2023:i:9:p:2033-:d:1132385
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/9/2033/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/11/9/2033/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Igor Litvinchev & Edith Lucero Ozuna Espinosa, 2014. "Integer Programming Formulations for Approximate Packing Circles in a Rectangular Container," Mathematical Problems in Engineering, Hindawi, vol. 2014, pages 1-6, March.
    2. Galiev, Shamil I. & Lisafina, Maria S., 2013. "Linear models for the approximate solution of the problem of packing equal circles into a given domain," European Journal of Operational Research, Elsevier, vol. 230(3), pages 505-514.
    3. Luiz J.P. Araújo & Ender Özcan & Jason A.D. Atkin & Martin Baumers, 2019. "Analysis of irregular three-dimensional packing problems in additive manufacturing: a new taxonomy and dataset," International Journal of Production Research, Taylor & Francis Journals, vol. 57(18), pages 5920-5934, September.
    4. Castillo, Ignacio & Kampas, Frank J. & Pintér, János D., 2008. "Solving circle packing problems by global optimization: Numerical results and industrial applications," European Journal of Operational Research, Elsevier, vol. 191(3), pages 786-802, December.
    5. Hifi, Mhand & Yousef, Labib, 2019. "A local search-based method for sphere packing problems," European Journal of Operational Research, Elsevier, vol. 274(2), pages 482-500.
    6. Ashish Raj & Yu-hsien Chen, 2011. "The Wiring Economy Principle: Connectivity Determines Anatomy in the Human Brain," PLOS ONE, Public Library of Science, vol. 6(9), pages 1-11, September.
    7. Mhand Hifi & Rym M'Hallah, 2009. "A Literature Review on Circle and Sphere Packing Problems: Models and Methodologies," Advances in Operations Research, Hindawi, vol. 2009, pages 1-22, July.
    8. A. Pankratov & T. Romanova & I. Litvinchev, 2019. "Packing ellipses in an optimized convex polygon," Journal of Global Optimization, Springer, vol. 75(2), pages 495-522, October.
    9. Romanova, Tatiana & Litvinchev, Igor & Pankratov, Alexander, 2020. "Packing ellipsoids in an optimized cylinder," European Journal of Operational Research, Elsevier, vol. 285(2), pages 429-443.
    10. Jie Wang, 1999. "Packing of Unequal Spheres and Automated Radiosurgical Treatment Planning," Journal of Combinatorial Optimization, Springer, vol. 3(4), pages 453-463, December.
    11. Yuriy Stoyan & Alexandr Pankratov & Tatiana Romanova & Giorgio Fasano & János D. Pintér & Yurij E. Stoian & Andrey Chugay, 2019. "Optimized Packings in Space Engineering Applications: Part I," Springer Optimization and Its Applications, in: Giorgio Fasano & János D. Pintér (ed.), Modeling and Optimization in Space Engineering, pages 395-437, Springer.
    12. Yuriy Stoyan & Alexandr Pankratov & Tatiana Romanova, 2017. "Placement Problems for Irregular Objects: Mathematical Modeling, Optimization and Applications," Springer Optimization and Its Applications, in: Sergiy Butenko & Panos M. Pardalos & Volodymyr Shylo (ed.), Optimization Methods and Applications, pages 521-559, Springer.
    13. A. Sutou & Y. Dai, 2002. "Global Optimization Approach to Unequal Global Optimization Approach to Unequal Sphere Packing Problems in 3D," Journal of Optimization Theory and Applications, Springer, vol. 114(3), pages 671-694, September.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Andreas Fischer & Igor Litvinchev & Tetyana Romanova & Petro Stetsyuk & Georgiy Yaskov, 2024. "Packing spheres with quasi-containment conditions," Journal of Global Optimization, Springer, vol. 90(3), pages 671-689, November.
    2. Josef Kallrath & Tatiana Romanova & Alexander Pankratov & Igor Litvinchev & Luis Infante, 2023. "Packing convex polygons in minimum-perimeter convex hulls," Journal of Global Optimization, Springer, vol. 85(1), pages 39-59, January.
    3. Lai, Xiangjing & Hao, Jin-Kao & Yue, Dong & Lü, Zhipeng & Fu, Zhang-Hua, 2022. "Iterated dynamic thresholding search for packing equal circles into a circular container," European Journal of Operational Research, Elsevier, vol. 299(1), pages 137-153.
    4. Romanova, Tatiana & Stoyan, Yurij & Pankratov, Alexander & Litvinchev, Igor & Plankovskyy, Sergiy & Tsegelnyk, Yevgen & Shypul, Olga, 2021. "Sparsest balanced packing of irregular 3D objects in a cylindrical container," European Journal of Operational Research, Elsevier, vol. 291(1), pages 84-100.
    5. Igor Litvinchev & Andreas Fischer & Tetyana Romanova & Petro Stetsyuk, 2024. "A New Class of Irregular Packing Problems Reducible to Sphere Packing in Arbitrary Norms," Mathematics, MDPI, vol. 12(7), pages 1-17, March.
    6. Alexander Pankratov & Tatiana Romanova & Igor Litvinchev, 2020. "Packing Oblique 3D Objects," Mathematics, MDPI, vol. 8(7), pages 1-17, July.
    7. Hifi, Mhand & Yousef, Labib, 2019. "A local search-based method for sphere packing problems," European Journal of Operational Research, Elsevier, vol. 274(2), pages 482-500.
    8. Bortfeldt, Andreas & Wäscher, Gerhard, 2013. "Constraints in container loading – A state-of-the-art review," European Journal of Operational Research, Elsevier, vol. 229(1), pages 1-20.
    9. Xiangyang Huang & LiGuo Huang, 2023. "Spreading Points Using Gradient and Tabu," SN Operations Research Forum, Springer, vol. 4(2), pages 1-11, June.
    10. Ambros Gleixner & Stephen J. Maher & Benjamin Müller & João Pedro Pedroso, 2020. "Price-and-verify: a new algorithm for recursive circle packing using Dantzig–Wolfe decomposition," Annals of Operations Research, Springer, vol. 284(2), pages 527-555, January.
    11. Frank J. Kampas & János D. Pintér & Ignacio Castillo, 2023. "Model Development and Solver Demonstrations Using Randomized Test Problems," SN Operations Research Forum, Springer, vol. 4(1), pages 1-15, March.
    12. Zhengguan Dai & Kathleen Xu & Melkior Ornik, 2021. "Repulsion-based p-dispersion with distance constraints in non-convex polygons," Annals of Operations Research, Springer, vol. 307(1), pages 75-91, December.
    13. Ryu, Joonghyun & Lee, Mokwon & Kim, Donguk & Kallrath, Josef & Sugihara, Kokichi & Kim, Deok-Soo, 2020. "VOROPACK-D: Real-time disk packing algorithm using Voronoi diagram," Applied Mathematics and Computation, Elsevier, vol. 375(C).
    14. Akang Wang & Chrysanthos E. Gounaris, 2021. "On tackling reverse convex constraints for non-overlapping of unequal circles," Journal of Global Optimization, Springer, vol. 80(2), pages 357-385, June.
    15. Stoyan, Yu. & Chugay, A., 2009. "Packing cylinders and rectangular parallelepipeds with distances between them into a given region," European Journal of Operational Research, Elsevier, vol. 197(2), pages 446-455, September.
    16. Akang Wang & Christopher L. Hanselman & Chrysanthos E. Gounaris, 2018. "A customized branch-and-bound approach for irregular shape nesting," Journal of Global Optimization, Springer, vol. 71(4), pages 935-955, August.
    17. Yizhe Yang & Bingshan Liu & Haochen Li & Xin Li & Xiaodong Liu & Gong Wang, 2023. "Automatic selection system of the building orientation based on double-layer priority aggregation multi-attribute decision-making," Journal of Intelligent Manufacturing, Springer, vol. 34(5), pages 2477-2493, June.
    18. Marić, Josip & Opazo-Basáez, Marco & Vlačić, Božidar & Dabić, Marina, 2023. "Innovation management of three-dimensional printing (3DP) technology: Disclosing insights from existing literature and determining future research streams," Technological Forecasting and Social Change, Elsevier, vol. 193(C).
    19. T. Kubach & A. Bortfeldt & H. Gehring, 2009. "Parallel greedy algorithms for packing unequal circles into a strip or a rectangle," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 17(4), pages 461-477, December.
    20. S. P. Li & Ka-Lok Ng, 2003. "Study Of The Unequal Spheres Packing Problem: An Application To Radiosurgery Treatment," International Journal of Modern Physics C (IJMPC), World Scientific Publishing Co. Pte. Ltd., vol. 14(06), pages 815-823.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:11:y:2023:i:9:p:2033-:d:1132385. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.