Methodology to Solve Multi-Dimentional Sphere Packing Problems
This paper discusses the problem of optimally packing spheres of various dimensions into containers of arbitrary geometrical shapes. According to the international classification, this problem belongs to Sphere Packing Problems (SPPs). The problem is to pack a set of spheres (circles, hyperspheres)...
Збережено в:
| Дата: | 2019 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English Russian |
| Опубліковано: |
Journal of Mechanical Engineering
2019
|
| Теми: | |
| Онлайн доступ: | https://journals.uran.ua/jme/article/view/160114 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Journal of Mechanical Engineering |
Репозитарії
Journal of Mechanical Engineering| id |
journalsuranuajme-article-160114 |
|---|---|
| record_format |
ojs |
| institution |
Journal of Mechanical Engineering |
| collection |
OJS |
| language |
English Russian |
| topic |
sphere hypersphere sphere packing knapsack problem open dimension problem nonlinear optimization UDC 519.85 шар гипершар упаковка шаров задача о рюкзаке задача с переменным размером нелинейная оптимизация УДК 519.85 куля гіперкуля упаковка куль задача про рюкзак задача зі змінним розміром нелінійна оптимізація УДК 519.85 |
| spellingShingle |
sphere hypersphere sphere packing knapsack problem open dimension problem nonlinear optimization UDC 519.85 шар гипершар упаковка шаров задача о рюкзаке задача с переменным размером нелинейная оптимизация УДК 519.85 куля гіперкуля упаковка куль задача про рюкзак задача зі змінним розміром нелінійна оптимізація УДК 519.85 Yaskov, G. N. Methodology to Solve Multi-Dimentional Sphere Packing Problems |
| topic_facet |
sphere hypersphere sphere packing knapsack problem open dimension problem nonlinear optimization UDC 519.85 шар гипершар упаковка шаров задача о рюкзаке задача с переменным размером нелинейная оптимизация УДК 519.85 куля гіперкуля упаковка куль задача про рюкзак задача зі змінним розміром нелінійна оптимізація УДК 519.85 |
| format |
Article |
| author |
Yaskov, G. N. |
| author_facet |
Yaskov, G. N. |
| author_sort |
Yaskov, G. N. |
| title |
Methodology to Solve Multi-Dimentional Sphere Packing Problems |
| title_short |
Methodology to Solve Multi-Dimentional Sphere Packing Problems |
| title_full |
Methodology to Solve Multi-Dimentional Sphere Packing Problems |
| title_fullStr |
Methodology to Solve Multi-Dimentional Sphere Packing Problems |
| title_full_unstemmed |
Methodology to Solve Multi-Dimentional Sphere Packing Problems |
| title_sort |
methodology to solve multi-dimentional sphere packing problems |
| title_alt |
Методология решения задач размещения многомерных шаров Методологія розв’язання задач розташування багатовимірних куль |
| description |
This paper discusses the problem of optimally packing spheres of various dimensions into containers of arbitrary geometrical shapes. According to the international classification, this problem belongs to Sphere Packing Problems (SPPs). The problem is to pack a set of spheres (circles, hyperspheres) with given radii into a container with given metric characteristics. The aim of this work is to create an integrated methodology for solving SPPs. The basic formulations of the problem are presented: in the form of the knapsack problem (KP), open dimension problem (ODP), and their corresponding mathematical models. The solution strategy selection is influenced by the form of problem statement, dimension of the space where the spheres are to be packed, metric peculiarities of the spheres (equal or unequal), number of the spheres to be packed, geometric shape of the container, presence of technological restraints, and count time limit. The structural elements of the methodology are mathematical models, methods for constructing initial packings, and methods of local and global optimization. In developing the solution method, we construct the initial feasible packings by using both the random and lattice methods, using a greedy algorithm and solving an auxiliary nonlinear programming problem. As local optimization methods, we consider the modifications of the feasible direction method, interior point method, Lagrange multiplier method, and method of optimization in groups of variables. For global optimization, we use the method of enumerating the subsets of spheres of a given set and method of enumerating the extreme points of the feasible region, which are implemented by using the branch and bound algorithm, the modifications of the decremental neighborhood search method, method of smooth transition from one local minimum to another by increasing problem dimensionality and introducing additional variable metric characteristics, solution method implemented as a sequence of non-linear programming problems of increasing dimensionality, and a multi-start method. Strategies for solving different SPP statements are proposed. |
| publisher |
Journal of Mechanical Engineering |
| publishDate |
2019 |
| url |
https://journals.uran.ua/jme/article/view/160114 |
| work_keys_str_mv |
AT yaskovgn methodologytosolvemultidimentionalspherepackingproblems AT yaskovgn metodologiârešeniâzadačrazmeŝeniâmnogomernyhšarov AT yaskovgn metodologíârozvâzannâzadačroztašuvannâbagatovimírnihkulʹ |
| first_indexed |
2024-06-01T14:44:05Z |
| last_indexed |
2024-06-01T14:44:05Z |
| _version_ |
1800670329988710400 |
| spelling |
journalsuranuajme-article-1601142019-04-03T19:19:45Z Methodology to Solve Multi-Dimentional Sphere Packing Problems Методология решения задач размещения многомерных шаров Методологія розв’язання задач розташування багатовимірних куль Yaskov, G. N. sphere hypersphere sphere packing knapsack problem open dimension problem nonlinear optimization UDC 519.85 шар гипершар упаковка шаров задача о рюкзаке задача с переменным размером нелинейная оптимизация УДК 519.85 куля гіперкуля упаковка куль задача про рюкзак задача зі змінним розміром нелінійна оптимізація УДК 519.85 This paper discusses the problem of optimally packing spheres of various dimensions into containers of arbitrary geometrical shapes. According to the international classification, this problem belongs to Sphere Packing Problems (SPPs). The problem is to pack a set of spheres (circles, hyperspheres) with given radii into a container with given metric characteristics. The aim of this work is to create an integrated methodology for solving SPPs. The basic formulations of the problem are presented: in the form of the knapsack problem (KP), open dimension problem (ODP), and their corresponding mathematical models. The solution strategy selection is influenced by the form of problem statement, dimension of the space where the spheres are to be packed, metric peculiarities of the spheres (equal or unequal), number of the spheres to be packed, geometric shape of the container, presence of technological restraints, and count time limit. The structural elements of the methodology are mathematical models, methods for constructing initial packings, and methods of local and global optimization. In developing the solution method, we construct the initial feasible packings by using both the random and lattice methods, using a greedy algorithm and solving an auxiliary nonlinear programming problem. As local optimization methods, we consider the modifications of the feasible direction method, interior point method, Lagrange multiplier method, and method of optimization in groups of variables. For global optimization, we use the method of enumerating the subsets of spheres of a given set and method of enumerating the extreme points of the feasible region, which are implemented by using the branch and bound algorithm, the modifications of the decremental neighborhood search method, method of smooth transition from one local minimum to another by increasing problem dimensionality and introducing additional variable metric characteristics, solution method implemented as a sequence of non-linear programming problems of increasing dimensionality, and a multi-start method. Strategies for solving different SPP statements are proposed. В статье рассматривается задача оптимального размещения шаров различной размерности в контейнерах произвольных геометрических форм. Согласно международной классификации эта задача относится к классу SPP (Sphere Packing Problems). Она заключается в размещении набора шаров (кругов, гипершаров) заданных радиусов в контейнере с заданными метрическими характеристиками. Целью данной работы является создание единой методологии решения задач SPP. Приведены основные постановки задачи: в виде задачи о рюкзаке; задачи с переменным размером контейнера и соответствующие математические модели. На выбор стратегии решения влияют вид постановки задачи, размерность пространства, в котором размещаются шары, метрические особенности шаров (равные или неравные), их количество, геометрическая форма контейнера, наличие технологических ограничений, ограничение на время счета. Структурными элементами методологии являются математические модели, способы построения начальных размещений, методы локальной и глобальной оптимизации. При разработке метода решения используется построение начальных допустимых размещений случайным, решетчатым способами, с помощью жадного алгоритма и путем решения вспомогательной задачи нелинейного программирования. В качестве методов локальной оптимизации рассматриваются модификации метода возможных направлений, метод внутренней точки, метод множителей Лагранжа и метод оптимизации по группам переменных. Для глобальной оптимизации используются метод перебора подмножеств шаров из заданного набора, метод перебора крайних точек области допустимых решений, реализованные с помощью алгоритма ветвей и границ, модификации методов сужающихся окрестностей, метод плавного перехода из одного локального минимума в другой на основе увеличения размерности задачи путем введения дополнительных переменных метрических характеристик, метод решения, реализованный в виде последовательности задач нелинейного программирования возрастающей размерности, метод мультистарта. Предложены стратегии решения задачи SPP для различных ее постановок. В статті розглядається задача оптимального розміщення куль різної розмірності в контейнерах довільних геометричних форм. Згідно з міжнародною класифікацією ця задача належить до класу SPP (Sphere Packing Problems). Вона полягає в розміщенні набору куль (кругів, гіперкуль) заданих радіусів у контейнері з заданими метричними характеристиками. Метою даної роботи є створення єдиної методології розв’язання задач SPP. Наведено основні постановки задачі: у вигляді задачі про рюкзак і задачі зі змінним розміром контейнера та відповідні математичні моделі. На вибір стратегії розв’язання впливають вид постановки задачі, розмірність простору, в якому розміщуються кулі, метричні особливості куль (рівні чи нерівні), кількість розміщуваних куль, геометрична форма контейнера, наявність технологічних обмежень, обмеження на час обчислень. Структурними елементами методології є математичні моделі, способи побудови початкових розміщень, методи локальної й глобальної оптимізації. Під час розробки методу розв'язання використовується побудова допустимих розміщень випадковим, ґратчастим способами, за допомогою жадібного алгоритму й шляхом розв’язання допоміжної задачі нелінійного програмування. Як методи локальної оптимізації розглядаються модифікації методу можливих напрямів, метод внутрішньої точки, метод множників Лагранжа та метод оптимізації за групами змінних. Для глобальної оптимізації використовуються метод перебору підмножин куль із заданого набору, метод перебору крайніх точок області допустимих розв’язків, реалізовані за допомогою алгоритму гілок і меж, модифікації методів околів, що звужуються, метод плавного переходу з одного локального мінімуму в інший на основі збільшення розмірності задачі шляхом уведення додаткових змінних метричних характеристик, метод розв’язання, реалізований у вигляді послідовності задач нелінійного програмування зростаючої розмірності, метод мультистарту. Запропоновано стратегії розв’язання задач SPP для різних її постановок. Journal of Mechanical Engineering Проблемы машиностроения Проблеми машинобудування 2019-03-19 Article Article application/pdf application/pdf https://journals.uran.ua/jme/article/view/160114 Journal of Mechanical Engineering; Vol. 22 No. 1 (2019); 67-75 Проблемы машиностроения; Том 22 № 1 (2019); 67-75 Проблеми машинобудування; Том 22 № 1 (2019); 67-75 2709-2992 2709-2984 en ru https://journals.uran.ua/jme/article/view/160114/161334 https://journals.uran.ua/jme/article/view/160114/161335 Copyright (c) 2019 G. N. Yaskov https://creativecommons.org/licenses/by-nd/4.0 |