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

A New Class of Irregular Packing Problems Reducible to Sphere Packing in Arbitrary Norms

Author

Listed:
  • Igor Litvinchev

    (Faculty of Mechanical and Electrical Engineering, Autonomous University of Nuevo Leon, San Nicolas de los Garza CP 66455, Mexico)

  • Andreas Fischer

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

  • Tetyana Romanova

    (A. Pidhornyi Institute for Mechanical Engineering Problems, National Academy of Sciences of Ukraine, 61046 Kharkiv, Ukraine
    Leeds University Business School, University of Leeds, Leeds LS2 9JT, UK)

  • Petro Stetsyuk

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

Abstract

Packing irregular objects composed by generalized spheres is considered. A generalized sphere is defined by an arbitrary norm. For three classes of packing problems, balance, homothetic and sparse packing, the corresponding new (generalized) models are formulated. Non-overlapping and containment conditions for irregular objects composed by generalized spheres are presented. It is demonstrated that these formulations can be stated for any norm. Different geometrical shapes can be treated in the same way by simply selecting a suitable norm. The approach is applied to generalized spheres defined by Lp norms and their compositions. Numerical solutions of small problem instances obtained by the global solver BARON are provided for two-dimensional objects composed by spheres defined in Lp norms to demonstrate the potential of the approach for a wide range of engineering optimization problems.

Suggested Citation

  • 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.
    • Handle: RePEc:gam:jmathe:v:12:y:2024:i:7:p:935-:d:1362014
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/7/935/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/12/7/935/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Leao, Aline A.S. & Toledo, Franklina M.B. & Oliveira, José Fernando & Carravilla, Maria Antónia & Alvarez-Valdés, Ramón, 2020. "Irregular packing problems: A review of mathematical models," European Journal of Operational Research, Elsevier, vol. 282(3), pages 803-822.
    2. Marina Prvan & Julije Ožegović & Arijana Burazin Mišura, 2019. "On Calculating the Packing Efficiency for Embedding Hexagonal and Dodecagonal Sensors in a Circular Container," Mathematical Problems in Engineering, Hindawi, vol. 2019, pages 1-16, July.
    3. 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.
    4. Huaqing Ma & Xiuhao Xia & Lianyong Zhou & Chao Xu & Zihan Liu & Tao Song & Guobin Zou & Yanlei Liu & Ze Huang & Xiaoling Liao & Yongzhi Zhao, 2023. "A Comparative Study of the Performance of Different Particle Models in Simulating Particle Charging and Burden Distribution in a Blast Furnace within the DEM Framework," Energies, MDPI, vol. 16(9), pages 1-21, May.
    5. 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.
    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. 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.
    8. Bennell, Julia A. & Oliveira, Jose F., 2008. "The geometry of nesting problems: A tutorial," European Journal of Operational Research, Elsevier, vol. 184(2), pages 397-415, January.
    9. Igor Litvinchev & Luis Infante & Lucero Ozuna, 2015. "Approximate Packing: Integer Programming Models, Valid Inequalities and Nesting," Springer Optimization and Its Applications, in: Giorgio Fasano & János D. Pintér (ed.), Optimized Packings with Applications, edition 1, chapter 0, pages 187-205, Springer.
    10. 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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. Hagspihl, Thomas & Kolisch, Rainer & Fontaine, Pirmin & Schiffels, Sebastian, 2024. "Apron layout planning–Optimal positioning of aircraft stands," Transportation Research Part B: Methodological, Elsevier, vol. 179(C).
    6. Iori, Manuel & de Lima, Vinícius L. & Martello, Silvano & Miyazawa, Flávio K. & Monaci, Michele, 2021. "Exact solution techniques for two-dimensional cutting and packing," European Journal of Operational Research, Elsevier, vol. 289(2), pages 399-415.
    7. Xiangyang Huang & LiGuo Huang, 2023. "Spreading Points Using Gradient and Tabu," SN Operations Research Forum, Springer, vol. 4(2), pages 1-11, June.
    8. 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.
    9. 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.
    10. Josef Kallrath & Joonghyun Ryu & Chanyoung Song & Mokwon Lee & Deok-Soo Kim, 2021. "Near optimal minimal convex hulls of disks," Journal of Global Optimization, Springer, vol. 80(3), pages 551-594, July.
    11. Umetani, Shunji & Murakami, Shohei, 2022. "Coordinate descent heuristics for the irregular strip packing problem of rasterized shapes," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1009-1026.
    12. Leao, Aline A.S. & Toledo, Franklina M.B. & Oliveira, José Fernando & Carravilla, Maria Antónia & Alvarez-Valdés, Ramón, 2020. "Irregular packing problems: A review of mathematical models," European Journal of Operational Research, Elsevier, vol. 282(3), pages 803-822.
    13. 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.
    14. 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.
    15. Chehrazad, Sahar & Roose, Dirk & Wauters, Tony, 2022. "A fast and scalable bottom-left-fill algorithm to solve nesting problems using a semi-discrete representation," European Journal of Operational Research, Elsevier, vol. 300(3), pages 809-826.
    16. Gun-Yeol Na & Jeongsam Yang, 2024. "Two-dimensional polygon classification and pairwise clustering for pairing in ship parts nesting," Journal of Intelligent Manufacturing, Springer, vol. 35(7), pages 3169-3184, October.
    17. Kimms, Alf & Király, Hédi, 2023. "An extended model formulation for the two-dimensional irregular strip packing problem considering general industry-relevant aspects," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1202-1218.
    18. 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.
    19. 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.
    20. Tollenaere, Jonas & Çalık, Hatice & Wauters, Tony, 2024. "Efficient use of collision detection for volume maximization problems," European Journal of Operational Research, Elsevier, vol. 319(3), pages 967-982.

    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:12:y:2024:i:7:p:935-:d:1362014. 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.