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 aim of this work is to create an integrated methodology fo...

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Проблеми машинобудування
Дата:	2019
Автор:	Yaskov, G.N.
Формат:	Стаття
Мова:	English
Опубліковано:	Інстиут проблем машинобудування ім. А.М. Підгорного НАН України 2019
Теми:	Applied mathematics
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/158842
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Methodology to Solve Multi-Dimentional Sphere Packing Problems / G.N. Yaskov // Проблеми машинобудування. — 2019. — Т. 22, № 1. — С. 67-75. — Бібліогр.: 37 назв. — англ, рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-158842
record_format	dspace
spelling	Yaskov, G.N. 2019-09-14T14:30:47Z 2019-09-14T14:30:47Z 2019 Methodology to Solve Multi-Dimentional Sphere Packing Problems / G.N. Yaskov // Проблеми машинобудування. — 2019. — Т. 22, № 1. — С. 67-75. — Бібліогр.: 37 назв. — англ, рос. 0131-2928 DOI: https://doi.org/10.15407/pmach2019.01.067 https://nasplib.isofts.kiev.ua/handle/123456789/158842 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 aim of this work is to create an integrated methodology for solving SPPs. В статті розглядається задача оптимального розміщення куль різної розмірності в контейнерах довільних геометричних форм. Згідно з міжнародною класифікацією ця задача належить до класу SPP (Sphere Packing Problems). Метою даної роботи є створення єдиної методології розв’язання задач SPP. В статье рассматривается задача оптимального размещения шаров различной размерности в контейнерах произвольных геометрических форм. Согласно международной классификации эта задача относится к классу SPP (Sphere Packing Problems). Целью данной работы является создание единой методологии решения задач SPP. en Інстиут проблем машинобудування ім. А.М. Підгорного НАН України Проблеми машинобудування Applied mathematics Methodology to Solve Multi-Dimentional Sphere Packing Problems Методологія розв’язання задач розташування багатовимірних куль Методология решения задач размещения многомерных шаров Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Methodology to Solve Multi-Dimentional Sphere Packing Problems
spellingShingle	Methodology to Solve Multi-Dimentional Sphere Packing Problems Yaskov, G.N. Applied mathematics
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
author	Yaskov, G.N.
author_facet	Yaskov, G.N.
topic	Applied mathematics
topic_facet	Applied mathematics
publishDate	2019
language	English
container_title	Проблеми машинобудування
publisher	Інстиут проблем машинобудування ім. А.М. Підгорного НАН України
format	Article
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 aim of this work is to create an integrated methodology for solving SPPs. В статті розглядається задача оптимального розміщення куль різної розмірності в контейнерах довільних геометричних форм. Згідно з міжнародною класифікацією ця задача належить до класу SPP (Sphere Packing Problems). Метою даної роботи є створення єдиної методології розв’язання задач SPP. В статье рассматривается задача оптимального размещения шаров различной размерности в контейнерах произвольных геометрических форм. Согласно международной классификации эта задача относится к классу SPP (Sphere Packing Problems). Целью данной работы является создание единой методологии решения задач SPP.
issn	0131-2928
url	https://nasplib.isofts.kiev.ua/handle/123456789/158842
citation_txt	Methodology to Solve Multi-Dimentional Sphere Packing Problems / G.N. Yaskov // Проблеми машинобудування. — 2019. — Т. 22, № 1. — С. 67-75. — Бібліогр.: 37 назв. — англ, рос.
work_keys_str_mv	AT yaskovgn methodologytosolvemultidimentionalspherepackingproblems AT yaskovgn metodologíârozvâzannâzadačroztašuvannâbagatovimírnihkulʹ AT yaskovgn metodologiârešeniâzadačrazmeŝeniâmnogomernyhšarov
first_indexed	2025-11-25T23:28:48Z
last_indexed	2025-11-25T23:28:48Z
_version_	1850581609290399744
fulltext	APPLIED MATHEMATICS ISSN 0131–2928. Journal of Mechanical Engineering, 2019, vol. 22, no. 1 УДК 519.85 МЕТОДОЛОГИЯ РЕШЕНИЯ ЗАДАЧ РАЗМЕЩЕНИЯ МНОГОМЕРНЫХ ШАРОВ Г. Н. Яськов, канд. техн. наук yaskov@ipmach.kharkov.ua ORCID: 0000-0002-1476-1818 Институт проблем машиностроения им. А. Н. Подгорного НАН Украины, 61046, Украина, г. Харьков, ул. Пожарского, 2/10 В статье рассматривается задача оптимального размещения шаров различной раз- мерности в контейнерах произвольных геометрических форм. Согласно международ- ной классификации эта задача относится к классу SPP (Sphere Packing Problems). Она заключается в размещении набора шаров (кругов, гипершаров) заданных радиусов в контейнере с заданными метрическими характеристиками. Целью данной работы является создание единой методологии решения задач SPP. Приведены основные по- становки задачи: в виде задачи о рюкзаке; задачи с переменным размером контейнера и соответствующие математические модели. На выбор стратегии решения влияют вид постановки задачи, размерность пространства, в котором размещаются шары, метрические особенности шаров (равные или неравные), их количество, геометриче- ская форма контейнера, наличие технологических ограничений, ограничение на время счета. Структурными элементами методологии являются математические модели, способы построения начальных размещений, методы локальной и глобальной оптими- зации. При разработке метода решения используется построение начальных допус- тимых размещений случайным, решетчатым способами, с помощью жадного алго- ритма и путем решения вспомогательной задачи нелинейного программирования. В качестве методов локальной оптимизации рассматриваются модификации метода возможных направлений, метод внутренней точки, метод множителей Лагранжа и метод оптимизации по группам переменных. Для глобальной оптимизации использу- ются метод перебора подмножеств шаров из заданного набора, метод перебора крайних точек области допустимых решений, реализованные с помощью алгоритма ветвей и границ, модификации методов сужающихся окрестностей, метод плавного перехода из одного локального минимума в другой на основе увеличения размерности задачи путем введения дополнительных переменных метрических характеристик, метод решения, реализованный в виде последовательности задач нелинейного про- граммирования возрастающей размерности, метод мультистарта. Предложены стратегии решения задачи SPP для различных ее постановок. Ключевые слова: шар, гипершар, упаковка шаров, задача о рюкзаке, задача с пе- ременным размером, нелинейная оптимизация. Введение Задачи оптимального размещения геометрических объектов являются задачами геометриче- ского проектирования [1]. Согласно международной классификации они относятся к классу задач раскроя и упаковки (C&P – cutting and packing) [2]. Одной из наиболее распространенных задач C&P является задача размещения шаров (SPP – sphere packing problem) различной размерности (2D – кру- ги, 3D – шары, nD – гипершары). Она заключается в размещении шаров из набора с заданными ра- диусами в заданном контейнере. При этом необходимо либо получить максимальный коэффициент заполнения контейнера, либо найти минимальный возможный размер контейнера. Задачи SPP имеют множество научных и практических применений, например, в текстильной, швейной, автомобильной, аэрокосмической и химической промышленности [3], в ядерной энергетике при моделировании процессов в ядерном реакторе [4], в аддитивном производстве для оптимизации геомет- рической формы детали [5] и в медицине для планирования автоматизированного радиохирургического лечения [6]. Размещения гипершаров используются для моделирования геометрии кристаллических со- стояний [7]. Также такие задачи возникают при численной оценке интегралов либо на поверхности сфе- ры, либо внутри нее [8]. Основным приложением задач размещения гипершаров является теория кодиро- вания, цифровая связь и хранение информации, например, CD, сотовые телефоны и Интернет [8, 9]. В зависимости от постановки задачи различают два основных класса задач SPP: задача о рюк- заке (KP – knapsack problem) и задача с переменным размером контейнера (ODP – open dimension problem) [2]. Задача KP состоит в размещении шаров из заданного набора в контейнере заданных фиксированных размеров с максимальным коэффициентом заполнения. В задаче ODP все шары из  Г. Н. Яськов, 2019 ПРИКЛАДНА МАТЕМАТИКА ISSN 0131–2928. Проблеми машинобудування, 2019, Т. 22, № 1 заданного набора необходимо разместить в контейнере, все размеры которого фиксированы, кроме одного, значение которого нужно минимизировать. Часть исследователей в своих работах [10–14] используют формулировку SPP в виде KP. При необходимости перейти к задаче ODP используется дихотомический поиск минимального размера контейнера, т.е. решается последовательность задач KP. При этом для поиска начальных точек ис- пользуются достаточно эффективные эвристические жадные алгоритмы (ЖА) [10, 11, 13, 14]. В работе [15] задача SPP формулируется как ODP. В качестве минимального размера контейне- ра используются радиус, длина, высота, периметр, площадь, объем, площадь поверхности. Предложена нелинейная математическая модель с дважды дифференцируемыми функциями, которая позволяет по- лучить локальный минимум задачи. Начальные размещения шаров выбираются случайным образом. В [16, 17] для решения задачи SPP, сформулированной в виде KP, используется математическая модель, основанная на увеличении размерности задачи. Предполагается, что радиусы шаров временно становятся переменными и максимизируется сумма объемов (площадей в 2D). Оптимизационный про- цесс продолжается до тех пор, пока радиусы шаров не достигнут своих исходных значений. Идея введения дополнительных переменных была использована и для задачи ODP для размещения неравных шаров [18, 19]. Дополнительные переменные улучшают распределение шаров в контейнере: там, где есть неиспользованное место, радиус шара может быть увеличен. Осуществляется переход из одной точки локального минимума в другую, с лучшим значением функции цели. При работе такого алгоритма важно найти связь между исходной и вспомогательной задачей с дополнительными переменными. При небольшом количестве шаров можно использовать методы полного перебора экстре- мальных точек задачи и теоретически получить глобальный экстремум. Однако на практике это за- трудняется сложностью решения систем нелинейных уравнений [20]. При увеличении количества размещаемых шаров размерность задачи растет пропорционально, а количество ограничений нелинейно. При большой размерности для решения задачи используются либо случайные размещения шаров [21], либо приближенные методы, основанные на декомпозиции задачи, например, с помощью метода оптимизации по группам переменных (МОГП) или ЖА [22, 23]. Таким образом, при различных постановках задачи размещения используются различные подходы и методы их решения. Однако до сих пор нет единой методологии решения таких задач. Поэтому целью этой работы является создание методологии решения задач размещения мно- гомерных шаров. Математические модели задачи размещения многомерных шаров Очевидно, что в первую очередь на выбор стратегии решения влияет вид постановки задачи. Рассмотрим постановки задач KP и ODP и их математические модели более подробно. Задача KP формулируется следующим образом. Пусть имеется контейнер dС R⊂ заданной геометрической формы с фиксированными размерами и набор шаров },...,2,1{ ,)( NIiuS N d ii =∈⊂ R , с заданными радиусами, где iu – вектор трансляции шара Ni IiS ∈ , , 2≥d – размерность пространст- ва. Задача заключается в размещении шаров из набора Nii IiuS ∈ ),( (всех или части из них) без взаимных наложений в контейнере С с максимальным коэффициентом заполнения. Предположим, что имеется K размеров шаров из набора Nii IiuS ∈ ),( с радиусами kr , },...,2,1{ KIk K =∈ . Обозначим количество шаров с радиусом kr , которые могут быть размещены внутри контейнера С как kn , KIk ∈ , и сгенерируем кортеж ),....,,( 21 Knnnt = . В кортеже t должен содержаться, по крайней мере, один ненулевой элемент kn , KIk ∈ . Обозначим множество всех возможных кортежей t как T . Мощность множества T ∏ = + K k kn 1 )1( . Сформируем подмножество t S шаров )( jj uS , },...,2,1{ nJj =∈ из набора Nii IiuS ∈ ),( в соответствии с кортежем ),....,,( 21 Knnnt = , где APPLIED MATHEMATICS ISSN 0131–2928. Journal of Mechanical Engineering, 2019, vol. 22, no. 1 ∑ = = K k knn 1 . Подмножество t S с учетом трансляции обозначается }),({)( JjvEvS jj t ∈= , где dn nvvvv R∈= ),...,,( 21 – вектор параметров размещения ),( jj vS ,Jj ∈ ),...,,( 21 djjjj xxxv = – вектор трансляции шара )( jj vS . Задача KP может быть сформулирована следующим образом. Найти подмножество шаров )(vS t , QIq ∈ , которое может полностью разместиться в контейнере С с максимальным коэффициентом заполнения ∑ ∈ ∈ == Jj d j Tt rtvFF )(max),( ** при условии TWtv dn ×⊂∈ R),( , (1) } ,0)( ,,, ,0),(:),{( JivjiJjivvtvW iijiij ∈≥Φ>∈≥Φ= , (2) где )( ii vΦ – Ф-функция для t i SS ∈ и объекта CRC int\ 2* = [24,25], ∑ = ≥+−−Φ d k jikjkijiij rrxxvv 1 22 0)()(=),( . Решение задачи (1)–(2) может быть сведено к перебору элементов множества T , для которых может быть найдена точка Wv ∈ . Поиск точки Wv ∈ может быть выполнен с помощью решения следующей оптимизационной задачи нелинейного программирования, в которой радиусы шаров являются переменными: ∑ ∈ =κ=κ Jj jrrv max),( *** при условии Mrv ∈),( , (3) где ),...,,( 21 nrrrr = ; { jiJjirrvvrvM jijiij nd <∈,≥,,Φ:∈= + ,, 0),(),( )1( R (4) 0),( ≥Φ iii rv , Ji ∈ , 0≥− irr , }Ji ∈ , 2 1 2 )(),( ji n k kjkijijiij rrxxrrvv +−−=,,Φ ∑ =       . Задача (3)–(4) является многоэкстремальной. Функция цели линейная, поэтому экстремумы на- ходятся в крайних точках области допустимых решений M (ОДР). Функция ),( jijiij rrvv ,,Φ является квадратичной формой. Вид функции ),( iii rvΦ зависит от геометрической формы контейнера. Теперь рассмотрим задачу ODP. Набор шаров Nii IiuS ∈ ),( , необходимо разместить в контей- нере С с минимальным размером (площадь, объем, или метрическая характеристика). Математическая модель задачи ODP [16] представляется как )(min* µ=µ f при условии λ+⊂∈µ,= dN WuY R ~ )( , (5) где µ – переменная метрическая характеристика (вектор переменных метрических характеристик); λ – количество переменных метрических характеристик ( 1=λ – в случае линейной характеристики, например, длина, высота и т.д., и 2≥λ , если размер контейнера задается несколькими метрическими характеристиками, например, площадь, площадь поверхности, объем); )(µf – функция, определяю- щая переменный размер контейнера С ( µ=µ)(f для 1=λ ); ПРИКЛАДНА МАТЕМАТИКА ISSN 0131–2928. Проблеми машинобудування, 2019, Т. 22, № 1 { }NiiNjiij dN IiuIjiuuYW ∈≥µΦ∈<<≥Φ∈= λ+ ,0),(,0,0),(: ~ R ; (6) ∑ = +−−Φ d k jikjkijiij rrxxuu 1 22 .)()(=),( Задача (5)–(6) является многоэкстремальной задачей нелинейного программирования. Методология решения задачи Методология решения оптимизационных задач размещения шаров основана на анализе постановки задачи, исходных данных и ограничений. Она включает в себя построение математических моделей, которые охватывают класс задач размещения шаров, исследование их особенностей и выработку стратегий решения поставленной задачи. Изучается структура, логические связи, предлагаемые методы и средства решения задачи. На выбор стратегии решения влияют следующие основные факторы: – вид постановки задачи (KP или ODP); – размерность пространства, в котором размещаются шары ( 2=d , 3=d и 4≥d ); – метрические особенности шаров (равные или неравные); – количество размещаемых шаров; – геометрическая форма контейнера; – наличие технологических ограничений; – ограничение на время счета. В зависимости от особенностей постановки задачи и математической модели предлагается стратегия решения задачи, структурными элементами которой являются: способы построения допустимых размещений (начальных точек или приближенных решений), методы локальной оптимизации и методы глобальной оптимизации. Предлагается использовать следующие способы построения допустимых размещений: случайный, решетчатый, жадный алгоритм, вспомогательная задача нелинейного программирования. Случайный способ заключается в случайном выборе координат центров шаров и проверке допустимости размещения [16]. В решетчатом способе центры шаров совпадают с узлами решетки [16, 23, 26]. При использовании ЖА, который является модификацией МОГП, происходит декомпозиция задачи на подзадачи [27]. В качестве группы переменных выбираются координаты одного шара, а функция цели может быть выбрана эвристически. Для получения допустимого размещения может также использоваться вспомогательная задача нелинейного программирования или последовательность таких задач [26]. В некоторых случаях целесообразно применить комбинации этих способов [16, 26]. В качестве методов локальной оптимизации в зависимости от особенностей математической модели и количества размещаемых шаров следует использовать модификации метода возможных направлений (МВН) [16, 23, 26], метод внутренней точки (МВТ) [18, 19, 28, 29], метод множителей Лагранжа (ММЛ) [30], МОГП [30]. Во всех методах целесообразно применять стратегию активного набора ограничений [31], благодаря которой значительно сокращаются вычислительные затраты. МВН дает возможность свести решение задачи нелинейного программирования к последовательности задач линейного программирования. Для задач SPP учитывается специфика ограничений: часть из них может быть линейными, матрицы первых и вторых производных являются сильно разреженными. Данные особенности делают возможность применить специальные пакеты программ [32, 33] и решать задачи достаточно большой размерности (5000–10000) переменных. При этом более устойчиво такие программы работают для шаров меньшей размерности 3≤d . МВТ разработан для решения задач нелинейного программирования и эффективно работает для задач средней размерности (до 1000 переменных). ММЛ применяется для поиска локального экстремума в комбинации с методом спуска и основан на анализе множителей Лагранжа активных ограничений. В случае размещения большого количества шаров (при количестве переменных больше 10000) следует использовать МОГП, выбирая по 1000–10000 переменных в группе. Для получения быстрого результата при ограничении на время счета можно выполнить локальную оптимизацию размещения APPLIED MATHEMATICS ISSN 0131–2928. Journal of Mechanical Engineering, 2019, vol. 22, no. 1 каждого шара отдельно, выбрав группу из d переменных, задающих координаты центра шара. Такой способ размещения называется еще методом последовательно-одиночного размещения [1] (sequential addition [22, 34]). Методы глобальной оптимизации представлены: методом перебора подмножеств шаров из заданного набора (МПШ), методом перебора крайних точек ОДР (МПКТ) на основании алгоритма ветвей и границ [20]; модификациями методов сужающихся окрестностей (МСО) [35, 36]; методом плавного перехода (МПП) из одного локального минимума в другой на основе увеличения размерности задачи путем введения дополнительных переменных метрических характеристик [18, 19, 29], методом решения, реализующим последовательность задач нелинейного программирования возрастающей размерности (МРПЗ) [16, 26]. Также может быть использована комбинация указанных методов. Для всех перечисленных методов применим метод мультистарта (ММС), который позволяет расширить выбор возможных вариантов размещения. МПШ используется для решения задачи KP. Для получения решения осуществляется перебор различных вариантов выбора подмножества шаров из заданного набора, который реализуется в виде дерева [37]. Для сокращения количества рассматриваемых вершин дерева используются правила отсечения, с помощью которых отбрасываются неперспективные вершины на основе анализа нижней и верхней оценок функции цели. В МПКТ рещаются все подсистемы из системы ограничений, т.е. исследуются все поверхности, описывающие границу ОДР. Для этого используется схема метода ветвей и границ. В случае линейной функции цели решение находится в одной из крайних точек ОДР. Если в задаче все ограничения обратно-выпуклые (например, размещение гипершаров в гиперпараллелепипеде), то крайняя точка определяется системой уравнений, количество которых равно количеству переменных задачи. С помощью модификаций МСО осуществляется оптимизация функции цели на различных перестановках шаров и дереве решений на основе вероятностных свойств функции цели. Теперь рассмотрим основные постановки и стратегии решения задачи. Задача KP. В случае, если рассматривается задача, сформулированная в виде KP, то для каждого выбранного варианта необходимо решить задачу (3)–(4) с помощью МВН и МВТ. При небольшом количестве шаров и размерности шаров 3≤d возможен и полный перебор крайних точек ОДР (МПКТ). Если количество шаров больше 10, то используется либо усеченное дерево решений, либо МРПЗ. При большом количестве шаров (больше 10000 переменных) используются различные модификации МОГП. Способ получения начального размещения зависит от размерности задачи, соотношения размеров шаров и контейнера и вида контейнера. Если решается задача размещения равных шаров, размер контейнера значительно больше размера шаров, а размерность задачи не больше четырех, то применяется решетчатый метод построения начального размещения. В других случаях используется либо случайный способ, либо специальный ЖА [26], например, при пошаговом процессе МРПЗ. Если контейнер имеет сложную геометрическую форму (например, при наличии большого количества зон запрета), то для получения начальной точки используется вспомогательная задача нелинейного программирования, решение которой позволяет восстановить допустимость из любой случайно выбранной точки, не принадлежащей контейнеру [26]. Наличие технологических ограничений, например ограничений на минимально и максимально допустимые расстояния, сужает область допустимых решений, а следовательно, и количество вариантов размещения. Обычно в этом случае не применяется решетчатый способ получения начальных размещений. Задача ODP. Для решения задач с переменным размером контейнера, сформулированных в виде (5)–(6), стратегия решения также зависит от числа размещаемых шаров и размерности задачи. Обычно в задачах ODP контейнер с зонами запрета не рассматривается. Если количество шаров не больше 10, а размерность шаров 3≤d , то используется МПКТ, реализованный в виде модификации алгоритма ветвей и границ [20]. Для решения систем уравнений используется метод Ньютона. В этом случае множество крайних точек включает в себя множество локальных экстремумов и нет необходимости применять метод локальной оптимизации. ПРИКЛАДНА МАТЕМАТИКА ISSN 0131–2928. Проблеми машинобудування, 2019, Т. 22, № 1 При увеличении количества шаров или увеличении размерности пространства необходимо использовать методы локальной оптимизации (МВН, МВТ), МСО и МПП, которые хорошо работают для задач средней размерности (10–300) шаров. Для задач большой размерности в качестве метода локальной оптимизации применим только алгоритм с использованием МВН, состоящий в решении последовательности задач линейного программирования (5000–10000 переменных). Для получения приближенного решения задачи необходимо применять МОГП. Этот же метод может быть использован для получения приближенных решений. В качестве способа получения начальных размещений используется решетчатый (для одинаковых шаров) и ЖА (для разных шаров). Следует отметить, что задача KP может быть решена как задача ODP, в которой минимизируется коэффициент гомотетии контейнера. Такой переход целесообразен при решении задач размещения неравных шаров. Он позволяет применять МПП для решения задач KP. Выводы Предложена единая методология решения задач размещения многомерных шаров. Методология является развитием теории геометрического проектирования и может использоваться специалистами в этой области для выбора стратегии решения задачи. С помощью разработанной методологии имеется возможность решать задачи размещения шаров, сформулированные как KP, так и ODP. Методология ориентирована на современные разработки в области геометрического проектирования и на использование мощных пакетов программ для решения задач линейного и нелинейного программирования. Литература 1. Стоян Ю. Г., Яковлев С. В. Математические модели и оптимизационные методы геометрического проек- тирования. Киев: Наук. думка, 1986. 268 с. 2. Waescher G., Haussner H. An improved typology of cutting and packing problems. Europ. J. Operational Re- search. 2007. Vol. 183. Iss. 5. P. 1109–1130. https://doi.org/10.1016/j.ejor.2005.12.047 3. Hifi M., M'Hallah R. A. literature review on circle and sphere packing problems: models and methodologies. Ad- vances in Operations Research. 2009. Vol. 2009. P. 1–19. doi: https://doi.org/10.1155/2009/150624 4. Snoj L., Ravnik M. Effect of packing fraction variations on the multiplication factor in pebble-bed nuclear reactors. Kerntechnik. 2006. Vol. 71. No. 4. P. 208–213. https://doi.org/10.3139/124.100295 5. Leary M., Merli L., Torti F., Mazur M., Brandt M. Optimal topology for additive manufacture: A method for ena- bling additive manufacture of support-free optimal structures. Materials and Design. 2014. Vol. 63. P. 678–690. https://doi.org/10.1016/j.matdes.2014.06.015 6. Blyuss O., Koriashkina L., Kiseleva E., Molchanov R. Optimal Placement of Irradiation Sources in the Planning of Radiotherapy: Mathematical Models and Methods of Solving. Computational and Math. Methods in Medicine. 2015. Vol. 2015. P. 1–8. https://doi.org/10.1155/2015/142987 7. Agapie S. C., Whitlock P. A. Random packing of hyperspheres and Marsaglia's parking lot test. Monte Carlo Methods and Appl. 2010. Vol. 16. Iss. 3–4. P. 197–209. doi: https://doi.org/10.1515/mcma.2010.019 8. Conway J. H., Sloane N. J. A. Sphere Packings, Lattices, and Groups. New York: Springer-Verlag, 1999. 706 p. https://doi.org/10.1007/978-1-4757-6568-7 9. Torquato S., Stillinger, F. H. Exactly solvable disordered sphere-packing model in arbitrary-dimensional Euclidean spaces. Physical Review E. 2006. Vol. 73. Iss. 3. P. 031–106. https://doi.org/10.1103/PhysRevE.73.031106 10. Hifi M., Yousef L. A dichotomous search-based heuristic for the three-dimensional packing problem. Cogent Eng.. 2015. Vol. 1. P. 1–15. https://doi.org/10.1080/23311916.2014.994257 11. Zeng Z., Yu X., He K., Huang W., Fu Z. Iterated Tabu Search and Variable Neighborhood Descent for packing un- equal circles into a circular container. Europ. J. Operational Research. 2016. Vol. 250. Iss. 2. P. 615–627. https://doi.org/10.1016/j.ejor.2015.09.001 12. Sutou A., Dai Y. Global Optimization Approach to Unequal Global Optimization Approach to Unequal Sphere Packing Problems in 3D. J. Optimization Theory and Appl. 2002. Vol. 114. Iss. 3. P. 671–694. doi: https://doi.org/10.1023/A:1016083231326 13. Zeng Z. Z, Huang W. Q., Xu R. C., Fu Z. H. An algorithm to packing unequal spheres in a larger sphere. Advanced Mate- rials Research. 2012. Vol. 546–547. P. 1464–1469. https://doi.org/10.4028/www.scientific.net/AMR.546-547.1464 14. Kubach T., Bortfeldt A., Tilli T., Gehring H. Greedy Algorithms for Packing Unequal Spheres into a Cuboidal Strip or a Cuboid. Asia-Pacific J. Operational Research. 2011. Vol. 28. No. 06. P. 739–753. https://doi.org/10.1142/S0217595911003326 APPLIED MATHEMATICS ISSN 0131–2928. Journal of Mechanical Engineering, 2019, vol. 22, no. 1 15. Birgin E. G., Sobral F. N. C. Minimizing the object dimensions in circle and sphere packing problems. Computers & Operations Research. 2008. Vol. 35. Iss. 7. P. 2357–2375. https://doi.org/10.1016/j.cor.2006.11.002 16. Stoyan Yu., Yaskov G. Packing congruent hyperspheres into a hypersphere. J. Global Optimization. 2012. Vol. 52. Iss. 4. P. 855–868. https://doi.org/10.1007/s10898-011-9716-z 17. Яковлев С. В., Яськов Г. Н., Коробчинский К. П. О методах переменного радиуса в задаче упаковки шаров в кон- тейнеры. Питання прикл. математики i мат. моделювання: зб. наук. пр. Дніпро: ЛІРА. 2017. № 17. С. 265–272. 18. Стоян Ю. Г., Шайтхауер Г., Яськов Г. Н. Упаковка неравных шаров в различные контейнеры. Кибернетика и систем. анализ. 2016. № 3. С. 97–105. 19. Yaskov G. N. Packing non-equal hyperspheres into a hypersphere of minimal radius. Проблемы машинострое- ния. 2014. Т. 17. № 1. С. 48–53. 20. Stoyan Y., Yaskov G. Mathematical model and solution method of optimization problem of placement of rectan- gles and circles taking into account special constraints. Intern. Transactions in Operational Research. 1998. Vol. 5. No. 1. P. 45–57. https://doi.org/10.1111/j.1475-3995.1998.tb00101.x 21. Visscher W. M., Bolsterli M. Random Packing of Equal and Unequal Spheres in Two and Three Dimensions. Na- ture. 1972. Vol. 239. P. 504–507. https://doi.org/10.1038/239504a0 22. Mueller G. E. Numerically packing spheres in cylinders. Powder Technology. 2005. Vol. 159. Iss. 2. P. 105–110. https://doi.org/10.1016/j.powtec.2005.06.002 23. Яськов Г. Н. Упаковка большого числа конгруэнтных кругов в цилиндре. Доп. НАН України. 2009. № 12. С. 43–49. 24. Chernov N., Stoyan Yu., Romanova T. Mathematical model and efficient algorithms for object packing problem. Computational Geometry. 2015. Vol. 43. Iss. 5. P. 535–553. https://doi.org/10.1016/j.comgeo.2009.12.003 25. Stoyan Y., Pankratov A., Romanova T. Quasi-phi-functions and optimal packing of ellipses. J. Global Optimiza- tion. 2016. Vol. 65. Iss. 2. P. 283–307. https://doi.org/10.1007/s10898-015-0331-2 26. Stoyan Y., Yaskov G. Packing equal circles into a circle with circular prohibited areas. Intern. J. Computer Mathe- matics. 2012. Vol. 89. Iss. 10. P. 1355–1369. https://doi.org/10.1080/00207160.2012.685468 27. Яськов Г. Н. Метод решения задачи размещения разных кругов с перспективным выбором начальных то- чек. Зб. наук. праць Харк. ун-ту повітряних сил. 2010. Вип. 3. №. 25. С. 119–122. 28. Wächter A., Biegler L. T. On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Math. Programming. 2006. Vol. 106. Iss. 1. P. 25–57. https://doi.org/10.1007/s10107-004-0559-y 29. Stoyan Yu., Yaskov G. Packing unequal circles into a strip of minimal length with a jump algorithm. Optimization Letters. 2014. Vol. 8. Iss. 3. P. 949–970. https://doi.org/10.1007/s11590-013-0646-1 30. Yaskov G. N. Random packing of identical spheres into a cylindrical container. Системи обробки інформації. 2008. Вип. 1. №. 68. С. 128–130. 31. Stoyan Y., Chugay A. Packing cylinders and rectangular parallelepipeds with distances between them into a given region. Europ. J. Operational Research. 2009. Vol. 197. Iss. 2. P. 446–455. https://doi.org/10.1016/j.ejor. 2008.07.003 32. Gondzio J. HOPDM (version 2.12) – a fast LP solver based on a primal-dual interior point method. Europ. J. Opera- tional Research. 1995. Vol. 85. Iss. 1. P. 221–225. https://doi.org/10.1016/0377-2217(95)00163-K 33. Meszaros C. On numerical issues of interior point methods. SIAM J. on Matrix Analysis and Appl. 2008. Vol. 30. Iss. 1. P. 223–235. https://doi.org/10.1137/050633354 34. Torquato S., Uche O. U., Stillinger, F. H. Random sequential addition of hard spheres in high Euclidean dimen- sions. Physical Review E. 2006. Vol. 74. Iss. 6. P. 061–308. https://doi.org/10.1103/PhysRevE.74.061308 35. Stoyan Y., Scheithauer G., Yaskov G. Packing of various radii solid spheres into a parallelepiped. Central Europ. J. Operations Research. 2003. Vol. 11. No. 4. 2003. P. 389–407. 36. Stoyan Y., Yaskov G. Packing Identical Spheres into a Rectangular Parallelepiped. In: Bortfeldt A., Homberger J., Kopfer H., Pankratz G., Strangmeier R. (eds) Intelligent Decision Support. Gabler, 2008. pp. 47–67. https://doi.org/10.1007/978-3-8349-9777-7_4 37. Яськов Г. Н. Дерево решений для задачи размещения неравных шаров в шаре заданного радиуса. Інформацій- ні системи і технології ІСТ-2017: пр 6-ї міжнар. наук.-техн. конф. (Коблеве, 11–16 вер. 2017). Коблеве, 2017. С. 143–144. Поступила в редакцию 14.01.2019

Methodology to Solve Multi-Dimentional Sphere Packing Problems

Репозитарії

Схожі ресурси