Размещено на http://www.allbest.ru/

Упаковка эллипсов в прямоугольник минимальных размеров

А.Н. Данилин, В.В. Комяк,

В.М. Комяк, А.В. Панкратов

Ключевые слова: упаковка, эллипсы, непрерывные повороты, квази-phi-функции, математическая модель, нелинейная оптимизация

Задачи упаковки и раскроя (Cutting & Packing) и являются предметом исследования вычислительной геометрии, а методы их решения - новым направлением теории исследования операций. Этот класс задач имеет широкий спектр научных и практических применений. В данной статье рассматривается класс задач упаковки заданного набора эллипсов в прямоугольный контейнер минимальных размеров, представляющий интерес, например, в порошковой металлургии при моделировании движения сыпучих веществ, задачах логистики при моделировании оптимальных упаковок объектов, имеющих форму цилиндра с эллиптическим основанием, в моделировании индивидуально-поточного движения людских и транспортных потоков и т.д.

Задачи оптимальной упаковки эллипсов относятся к классу NP-сложных. Для решения задач такого класса используются, как правило, эвристические алгоритмы. Разработка эффективных алгоритмов, основанных на применении методов локальной и глобальной оптимизации, требует построения адекватных математических моделей, основанных на аналитическом описании отношений эллипсов с учетом их непрерывных трансляций и вращений.

Анализ последних исследований и публикаций. Верхняя оценка плотности упаковки эллипсов в контейнер получена еще в работе [1]. В работах [2, 3] для решения задач данного класса применяется метод дискретного элемента. Однако данный метод является достаточно ресурсоемким, что ограничивает размерность пространства решения и количество используемых частиц. Математическая модель упаковки двух эллипсов исследуется в статье [4]. Эффективный численный алгоритм для определения факта пересечения эллипсов приводится в статье [5], там же исследуется влияние размеров эллипсов на плотность упаковки.

В статье [6] предлагается метод решения задачи упаковки эллипсов, допускающих вращения, с использованием современных NLP решателей (solvers), доступных в GAMS. В этой статье приводится достаточно полный обзор литературы, посвященный задачам упаковки эллипсов. Для аналитического описания условий непересечения неориентированных эллипсов авторы используют идею разделяющей прямой, предложенную в работе [7] для моделирования отношений кругов и выпуклых многоугольников. В [6] получено глобальное решение для небольшого числа эллипсов (), однако при n>14 авторам не удалось получить допустимого решения. В этой связи авторы предлагают эвристический polylithic-алгоритм для размещения большего числа эллипсов (до 100) в прямоугольной области фиксированной ширины и переменной длины.

Задача оптимальной упаковки эллипсов, допускающих непрерывные вращения, рассмотрена в [8], [9]. Для аналитического описания основных ограничений размещения используются свободные от радикалов квази-phi-функции и псевдонормализованные квази-phi-функции [10], [11]. В этих работах строится математическая модель в виде задачи нелинейного программирования. Предлагаются эффективные алгоритмы поиска локальных экстремумов. Подход, изложенный в работах [8] и [9], позволяет представить задачу оптимальной упаковки эллипсов с учетом допустимых расстояний в виде задачи нелинейного программирования и получать локально-оптимальные решения при . Авторам [9] удалось улучшить результаты по времени и значению функции цели для многих тестовых примеров, приведенных в статье [6].

В фундаментальном исследовании [12] рассмотрены вопросы упаковки, как эллипсов, так и эллипсоидов в различных выпуклых областях. При моделировании условий непересечения объектов исследуются два подхода: первый основан на идее разделяющей прямой (плоскости) из [6], а второй - на использовании афинных преобразований пространства . При использовании второго подхода в результате афинных преобразований пространства один из эллипсов (эллипсоидов) преобразуется в круг (шар), второй - в некоторый эллипс (эллипсоид). После указанных преобразований для формализации условий непересечения полученных объектов используется идея метода, разработанного в [13] для моделирования геометрических отношений круга и эллипса. Генерация "хороших" стартовых точек и применение солвера Algencan [14] для решения задач нелинейного программирования позволило авторам [12] улучшить большинство результатов работ [6], [9].

Оригинальный подход к моделированию задачи упаковки эллипсов, основанный на использовании множителей Лагранжа, предложен в работах [15] и [16], однако тестирование показало меньшую эффективность предложенного метода, чем в работах [9], [12]. К тому же описание в аналитическом виде условий размещения эллипса в круге, предложенные в [15], содержат ошибку.

Однако запись в аналитическом виде условий непересечения каждой пары эллипсов в перечисленных работах довольно громоздка и/или осуществляется при помощи системы нелинейных неравенств.

В работе предлагается подход, основанный на математическом моделировании отношений между эллипсами (непересечение и расположение на минимально допустимом расстоянии) с использованием новой квази-phi-функции, что позволило сформулировать такие условия в виде единственного сравнительно несложного нелинейного неравенства. Данный подход позволяет представить задачу оптимальной упаковки эллипсов с учетом допустимых расстояний в виде задачи нелинейного программирования и эффективно получать локально оптимальные решения задачи. упаковка раскрой геометрия алгоритм

Постановка задачи и ее решение. Предметом исследования данной статьи является задача упаковки в следующей постановке. Пусть задана прямоугольная область переменной длины и переменной ширины , и набор эллипсов , , которые должны размещаться внутри области Щ. Полагаем, что система координат контейнера Щ фиксирована и совпадает с глобальной системой координат. Каждый эллипс задан большой и малой полуосями и . Центр эллипса совпадает с началом его собственной системы координат. Положение эллипса характеризуется вектором переменных параметров размещения объекта , где - вектор трансляции, - угол поворота. Обозначим - эллипс , повернутый на угол и транслированный на вектор .

Между эллипсами и могут быть заданы ограничения на минимально допустимые расстояния , а между эллипсом и границей контейнера Щ - ограничения на минимально допустимые расстояния.

Задача упаковки эллипсов. Разместить с учетом ограничений на заданные допустимые расстояния множество эллипсов , , в прямоугольном контейнере минимальной площади .

В данном исследовании, как и в работах [8] и [9], в качестве эффективного средства математического моделирования отношений непересечения пары эллипсов предлагается использовать функцию из класса квази-phi-функций (см. [10], [11]).

Согласно определению, квази-phi-функцией для объектов и называется всюду определенная непрерывная по всем переменным функция, для которой функция является phi-функцией объектов и . Здесь - вектор вспомогательных переменных, принадлежащих некоторому подмножеству пространства (как будет показано ниже, в данном случае , а совпадает с ).

Далее мы используем следующую важную характеристику квази-phi-функции: если для некоторого выполняется , то (см. [9], [10] для более подробной информации).

Предлагаемая квази-phi-функция основывается на использовании следующего утверждения: если выпуклые объекты не пересекаются, то существует такая проходящая через цент системы координат прямая, что проекции объектов на эту прямую не пересекаются.

В самом деле, пусть выпуклые объекты и не имеют общих внутренних точек (Рис. 1).

Рис. 1. Иллюстрация к построению квази-phi-функции .

Тогда, согласно теореме о разделяющей прямой, существует прямая , разбивающая плоскость на две полуплоскости таким образом, что объекты и лежат в разных полуплоскостях. Следовательно, проекции множеств и на любую прямую, перпендикулярную , не пересекаются (не имеют общих внутренних точек в ). Обозначим прямую, перпендикулярную и проходящую через центр системы координат и - угол между прямой и осью .

Повернув прямую вместе с проекциями эллипсов и (с центрами в точках и соответственно) вокруг точки на угол , получим проекции эллипсов и с центрами в точках и .

Таким образом, условие непересечения эллипсов и эквивалентно условию

, (1)

где

, (2)

(3)

, (4)

. (5)

Замечание. Если эллипсы не пересекаются и после приведенных операций , то в качестве угла поворота прямой следует взять угол .

С учетом вышесказанного, условие взаимного непересечения эллипсов описывается неравенством

,

где квази-phi-функция может быть записана в виде

,

или, с учетом (1)-(5),

. (6)

Следует отметить, что квази-phi-функция (6) нормализованна, т.е. является нормализованной phi-функцией объектов и и по значению совпадает с расстоянием между объектами и . В самом деле, пусть расстояние между и равно . Это означат, что существуют две точки и такие, что расстояние между ними равно (Рис. 2).

Рис. 2. Иллюстрация к доказательству нормализованности квази-phi-функции .

Построим отрезок . Отметим, что по способу построения отрезок параллелен нормали к объекту в точке и нормали к объекту в точке . Тогда в качестве прямой может быть выбрана прямая, проходящая через точку параллельно отрезку .

Очевидно, что расстояние между проекциями точек и на прямую равно и что при любом другом угле наклона прямой расстояние между проекциями точек на прямую будет меньше .

Нормализованность квази-phi-функции (6) означает, что соблюдение условий минимально допустимых расстояний между эллипсами и обеспечивается выполнением неравенства .

Для формализации условий принадлежности эллипса области Щ воспользуемся нормализованной phi-функцией , описывающей условия непересечения объектов и . Функцию предлагается построить на основе аналитического описания условий принадлежности Щ проекций на оси глобальной системы координат (Рис. 3).

Рис. 3. Формализация условий размещения эллипса в области.

Так, эллипс принадлежит прямоугольной области с размерами , если неотрицательна phi-функция

(7)

где

,

.

Таким образом, с учетом нормализованности функций (6) и (7), математическая модель задачи упаковки эллипсов в прямоугольный контейнер Щ минимальной площади может быть сформулирована в виде

(8)

, (9)

где

, ,

,

,

Следует отметить, что хотя в неравенствах, описывающих область допустимых решений , и встречаются радикалы, подкоренные выражения строго положительны на всей области определения.

Задача условной оптимизации (8) - (9) является NP-трудной задачей нелинейного программирования. Область допустимых решений имеет сложную структуру: это, вообще говоря, несвязное множество, каждая компонента связности является многосвязной, граница состоит из нелинейных поверхностей, содержащих овраги. Матрица системы неравенств, задающих , сильно разреженна и имеет блочную структуру.

Задача (8) - (9) представляет собой точную формулировку задачи упаковки эллипсов. Построенная модель описывает невыпуклую и непрерывную задачу нелинейного программирования. Область определения содержит все глобально-оптимальные решения. Можно, по крайней мере теоретически, использовать для решения такой задачи глобальные решатели задач нелинейного программирования и получить решение, которое является оптимальной упаковкой.

Однако на практике мы имеем дело с большим числом переменных и количеством неравенств в модели. В результате поиск даже локально-оптимального решения, не говоря уже о глобальном экстремуме, при большом числе эллипсов становится труднореализуемой задачей для NLP решателей при решении задачи вида (8)-(9) непосредственно. Так, авторам [6] не удалось получить допустимое решение задачи при использовании решателей BARON, LindoGlobal и GloMIQO при Для поиска "достаточно хорошей" локально-оптимальной упаковки эллипсов за разумное временя вычислений в [8], [9] предложен и разработан подход, позволяющий существенно повысить вероятность нахождения локального экстремума задачи при одновременном значительном сокращении затрат вычислительных ресурсов.

В соответствии с разработанной в [8], [9] методикой, стратегия решения задачи (8)-(9) состоит из следующих шагов:

Шаг 1. Генерируется набор стартовых точек из области допустимых решений задачи (8)-(9), используя модифицированный алгоритм SPA из [8]. При этом изменению подвергнут только шаг алгоритма, касающийся поиска допустимых значений дополнительных переменных для квази-phi-функци.

Шаг 2. Осуществляется поиск локального минимума функции цели задачи (8)-(9), стартуя из точек, полученных на шаге 1, с применением описанной в [8] процедуры LOFRT локальной оптимизации с преобразованием области допустимых решений.

В то время как имеется пар эллипсов, предложенный подход в большинстве случаев позволяет оперировать на каждом этапе парами, так как для каждого эллипса должны быть проверены только условия непересечения с ближайшими соседями.

Шаг 3. В качестве приближения к оптимальному решению задачи (8) - (9) выбирается лучшее локальное решение из вариантов, полученных на шаге 2.

Важной частью предложенного в [8] подхода к решению задачи является LOFRT процедура, позволяющая сократить затраты вычислительных ресурсов благодаря сведению задачи (8)-(9) к последовательности подзадач меньшей размерности и с меньшим количеством ограничений.

Был проведен ряд вычислительных экспериментов. Рассмотрено 50 эллипсов (n=50). Так для тестового примера ТС 50 ({(2,1.5);(1.5,1);(1,0.8);(0.9,0.75);(0.8,0.6);(0.7,0.3)}{(a_i,b_i)=(1,0.8), i = 7,…,50}), впервые решенного в [6], применение новой квази-phi-функции привело к уменьшению среднего времени получения одного локального экстремума (301.25 сек.) приблизительно в 2.5 раза. При этом в ходе тестирования было получено рекордное на сегодняшний день значение функции цели 152.602. Полученное решение представлено на рис. 4.

Вычислительные эксперименты проводились на AMD Athlon 64x2 Dual 5200+. Решение подзадач нелинейного программирования осуществлялось с помощью программы IPOPT [17], доступной на открытом некоммерческом ресурсе (https://projects.coin-or.org/Ipopt) .

Таким образом, предложенная стратегия решения задачи (8)-(9) позволяет эффективно получать локально оптимальные решения при . Для задач с большим числом эллипсов решение возможно, но с большими затратами вычислительных ресурсов.

Рис. 4 Локальный экстремум задачи упаковки 50 эллипсов.

Следует отметить, что процедура LOFRT представляет собой реализацию так называемого compaction-алгоритма и может быть использована непосредственно для улучшения приближенных решений, полученных другими авторами и методами.

Выводы

Итак, предложенные новые phi-функции и квази-phi-функции для аналитического описания условий непересечения эллипсов и принадлежности эллипса области, допускающие непрерывные вращения и трансляции эллипсов и учитывающие возможность наличия минимально допустимых расстояний между ними, а также алгоритм поиска локально-оптимальных решений позволяют сокращать затраты вычислительных ресурсов, что дает возможность решать практические задачи большей размерности и улучшать приближенные решения, полученные другими авторами и методами.

Литература

1. Toth L.F. Packing of ellipses with continuously distributed area / L.F. Toth // Journal of Discrete Mathematics - 1986. - Vol. 60. - P. 263-267. doi:10.1016/0012-365X(86)90018-X.

2. Ting J.M. An ellipse-based discrete element model for granular materials / J.M. Ting, M. Khwaja, L. R. Meachum, J.D. Rowell // Numerical and Analytical Methods in Geomechanics. - 1993. - Vol. 17(9). - P. 603-623. doi:10.1002/nag.1610170902.

3. Feng Y. An Advancing Front Packing of Polygons, Ellipses and Spheres / Y. Feng, K. Han, D. Owen // Discrete Element Methods - 2002. - P. 93-98. doi:10.1061/40647(259)17.

4. Vickers, G. T. / Nested Ellipses // Applied Probability Trust. - 2009. - Vol. 41(3). - P. 131-137.

5. Xu W.X. An overlapping detection algorithm for random sequential packing of elliptical particles / W.X. Xu, H.S. Chen, Z. Lv // Physica. - 2011 - Vol. 390. - P. 2452-2467. doi:10.1016/j.physa.2011.02.048.

6. Kallrath J. Cutting Ellipses from Area-Minimizing Rectangles / J. Kallrath, S. Rebennack // Journal of Global Optimization. - 2013. - Vol. 59 (2-3). - P. 405-437. doi:10.1007/s10898-013-0125-3.

7. Kallrath, J. Cutting Circles and Polygons from Area-Minimizing Rectangles / J. Kallrath // Journal of Global Optimization - 2008. - Vol. 43 (2-3). - P. 299-328. doi:10.1007/s10898-007-9274-6.

8. Панкратов А.В. / Оптимальная упаковка эллипсов с учетом допустимых расстояний / А.В. Панкратов, Т.Е. Романова, И.А. Суббота // Журнал обчислювальної математики. - 2014. - T. 1 - C. 27-42.

9. Stoyan, Yu. Quasi-phi-functions and optimal packing of ellipses / Yu. Stoyan, A. Pankratov, T. Romanova // J. of Global Optimization. - 2016. - Vol. 65(2) - P. 283 - 307.

10. Стоян Ю.Г. Квази-phi-функции для математического моделирования отношений геометрических / Ю.Г. Стоян, А.В. Панкратов, Т.Е. Романова, Н.И. Чернов // Доповіді Національної академії наук України. - 2014. - T. 9. - C. 49-54.

11. Stoyan, Yu. Optimized Object Packings Using Quasi-Phi-Functions / Yu. Stoyan, T. Romanova, A. Pankratov, A. Chugay. Yu. Stoyan, T. Romanova, A. Pankratov, A. Chugay // Volume 105 of the series Springer Optimization and Its Applications, -2015. pp 265-293.

12. Birgin E.G. Packing Ellipsoids by Nonlinear Optimization / E.G. Birgin, R. Lobato, J.M. Martнnez // Journal of Global Optimization 65, 709-743, 2016.

13. Birgin E.G. Packing circles within ellipses / E G. Birgin, L.H. Bustamante, H.F. Callisaya, J.M. Martэnez E.G. Birgin, L.H. Bustamante, H.F. Callisaya, J.M. Martэnez // International transactions in operational research. - 2013. - Vol. 20(3). - P. 365-389. doi:10.1111/itor.12006.

14. Birgin E. G. Practical Augmented Lagrangian Methods for Constrained Optimization / E. G. Birgin and J. M. Martinez // Society for Industrial and Applied Mathematics, Philadelphia, PA, 2014.

15. Kampas Frank J. General Ellipse Packings in an Optimized Circle Using Embedded Lagrange Multipliers (Submitted for publication January 2016) / Frank J. Kampas, Jбnos D. Pintйr, Ignacio Castillo, Jбnos D. Pintйr, Ignacio Castillo // Global Optimization Submissions - 2016, (http://www.optimization-online.org/DB_FILE/2016/01/5293.pdf).

16. Kampas Frank J. General Ellipse Packings in Optimized Regular Polygons, (Submitted for publication February 2016) / Frank J. Kampas, Ignacio Castillo, Jбnos D. Pintйr // Global Optimization Submissions - 2016, (http://www.optimization-online.org/DB_FILE/2016/03/5348.pdf).

17. Wachter A. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming / A. Wachter, L.T. Biegler // Mathematical Programming. - 2006. - Vol. 106 (1). - P. 25-57. doi:10.1007/s10107-004-0559-y.

Размещено на Allbest.ru