IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v90y2024i3d10.1007_s10898-024-01412-1.html
   My bibliography  Save this article

Packing spheres with quasi-containment conditions

Author

Listed:
  • Andreas Fischer

    (Technische Universität Dresden)

  • Igor Litvinchev

    (Autonomous University of Nuevo León)

  • Tetyana Romanova

    (National Academy of Sciences of Ukraine
    Kharkiv National University of Radio Electronics)

  • Petro Stetsyuk

    (National Academy of Sciences of Ukraine)

  • Georgiy Yaskov

    (National Academy of Sciences of Ukraine)

Abstract

A novel sphere packing problem is introduced. A maximum number of spheres of different radii should be placed such that the spheres do not overlap and their centers fulfill a quasi-containment condition. The latter allows the spheres to lie partially outside the given cuboidal container. Moreover, specified ratios between the placed spheres of different radii must be satisfied. A corresponding mixed-integer nonlinear programming model is formulated. It enables the exact solution of small instances. For larger instances, a heuristic strategy is proposed, which relies on techniques for the generation of feasible points and the decomposition of open dimension problems. Numerical results are presented to demonstrate the viability of the approach.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:jglopt:v:90:y:2024:i:3:d:10.1007_s10898-024-01412-1
    DOI: 10.1007/s10898-024-01412-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-024-01412-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-024-01412-1?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    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. 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.
    3. 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.
    4. Andreas Fischer & Guntram Scheithauer, 2015. "Cutting and Packing Problems with Placement Constraints," Springer Optimization and Its Applications, in: Giorgio Fasano & János D. Pintér (ed.), Optimized Packings with Applications, edition 1, chapter 0, pages 119-156, Springer.
    5. A. Grosso & A. Jamali & M. Locatelli & F. Schoen, 2010. "Solving the problem of packing equal and unequal circles in a circular container," Journal of Global Optimization, Springer, vol. 47(1), pages 63-81, May.
    6. 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.
    7. Tatiana Romanova & Yuri Stoyan & Alexandr Pankratov & Igor Litvinchev & Konstantin Avramov & Marina Chernobryvko & Igor Yanchevskyi & Irina Mozgova & Julia Bennell, 2021. "Optimal layout of ellipses and its application for additive manufacturing," International Journal of Production Research, Taylor & Francis Journals, vol. 59(2), pages 560-575, January.
    8. Yaohua He & Yong Wu, 2013. "Packing non-identical circles within a rectangle with open length," Journal of Global Optimization, Springer, vol. 56(3), pages 1187-1215, July.
    9. Frank J. Kampas & János D. Pintér & Ignacio Castillo, 2020. "Packing ovals in optimized regular polygons," Journal of Global Optimization, Springer, vol. 77(1), pages 175-196, May.
    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.
    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, 2023. "Quasi-Packing Different Spheres with Ratio Conditions in a Spherical Container," Mathematics, MDPI, vol. 11(9), pages 1-19, April.
    2. 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.
    3. 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).
    4. 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.
    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. 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.
    7. López, C.O. & Beasley, J.E., 2016. "A formulation space search heuristic for packing unequal circles in a fixed size circular container," European Journal of Operational Research, Elsevier, vol. 251(1), pages 64-73.
    8. Xiangjing Lai & Jin-Kao Hao & Renbin Xiao & Fred Glover, 2023. "Perturbation-Based Thresholding Search for Packing Equal Circles and Spheres," INFORMS Journal on Computing, INFORMS, vol. 35(4), pages 725-746, July.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. I Al-Mudahka & M Hifi & R M'Hallah, 2011. "Packing circles in the smallest circle: an adaptive hybrid algorithm," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(11), pages 1917-1930, November.
    14. 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.
    15. Xiangyang Huang & LiGuo Huang, 2023. "Spreading Points Using Gradient and Tabu," SN Operations Research Forum, Springer, vol. 4(2), pages 1-11, June.
    16. Piotr Sawicki & Hanna Sawicka & Marek Karkula & Krzysztof Zajda, 2025. "Combined Rough Sets and Rule-Based Expert System to Support Environmentally Oriented Sandwich Pallet Loading Problem," Energies, MDPI, vol. 18(2), pages 1-48, January.
    17. Ta Thi Nguyet Trang & Pham Chien Thang & Le Dinh Hai & Vi Thi Phuong & Tran Quang Quy, 2024. "Understanding the Adoption of Artificial Intelligence in Journalism: An Empirical Study in Vietnam," SAGE Open, , vol. 14(2), pages 21582440241, May.
    18. Alexander Pankratov & Tatiana Romanova & Igor Litvinchev, 2020. "Packing Oblique 3D Objects," Mathematics, MDPI, vol. 8(7), pages 1-17, July.
    19. Zeng, Zhizhong & Yu, Xinguo & He, Kun & Huang, Wenqi & Fu, Zhanghua, 2016. "Iterated Tabu Search and Variable Neighborhood Descent for packing unequal circles into a circular container," European Journal of Operational Research, Elsevier, vol. 250(2), pages 615-627.
    20. Oslandsbotn, Andreas & Kereta, Željko & Naumova, Valeriya & Freund, Yoav & Cloninger, Alexander, 2022. "StreaMRAK a streaming multi-resolution adaptive kernel algorithm," Applied Mathematics and Computation, Elsevier, vol. 426(C).

    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:spr:jglopt:v:90:y:2024:i:3:d:10.1007_s10898-024-01412-1. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.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.