NLP-задача упаковки гомотетичних еліпсів у прямокутний контейнер
Розглядається проблема упаковки гомотетичних одинаково орієнтованих еліпсів у прямокутному контейнері мінімальної площі (або периметра). Наведено її формулювання у вигляді багатоекстремальної задачі нелінійного програмування. Для пошуку локальних екстремумів запропоновано два алгоритми: з використан...
Saved in:
| Date: | 2014 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Series: | Теорія оптимальних рішень |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/111521 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | NLP-задача упаковки гомотетичних еліпсів у прямокутний контейнер / П.І. Стецюк, Т.Є. Романова, І.О. Субота // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 139-146. — Бібліогр.: 12 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-111521 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1115212017-01-11T03:03:24Z NLP-задача упаковки гомотетичних еліпсів у прямокутний контейнер Стецюк, П.І. Романова, Т.Є. Субота, І.О. Розглядається проблема упаковки гомотетичних одинаково орієнтованих еліпсів у прямокутному контейнері мінімальної площі (або периметра). Наведено її формулювання у вигляді багатоекстремальної задачі нелінійного програмування. Для пошуку локальних екстремумів запропоновано два алгоритми: з використанням IPOPT та модифікації r-алгоритму. Наводяться результати обчислювальних експериментів. Рассматривается проблема упаковки гомотетичных одинаково ориентированных эллипсов в прямоугольном контейнере минимальной площади (или периметра). Дана ее формулировка в виде многоэкстремальной задачи нелинейного программирования. Для поиска локальных экстремумов предлагаются два алгоритма: с использованием IPOPT и модификации r-алгоритма. Приводятся результаты вычислительных экспериментов. The paper considers a packing problem of a finite set of homothetic ellipses into a rectangular container of the minimal perimeter (area). We formulate the problem in the form of a multiextremal nonlinear programming one. In order to search for local extrema of the problem we propose two algorithms. One algorithm uses IPOPT and the other algorithm based on a modification of the r-algorithm. The results of computational experiments are given. 2014 Article NLP-задача упаковки гомотетичних еліпсів у прямокутний контейнер / П.І. Стецюк, Т.Є. Романова, І.О. Субота // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 139-146. — Бібліогр.: 12 назв. — укр. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/111521 519.8 uk Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| description |
Розглядається проблема упаковки гомотетичних одинаково орієнтованих еліпсів у прямокутному контейнері мінімальної площі (або периметра). Наведено її формулювання у вигляді багатоекстремальної задачі нелінійного програмування. Для пошуку локальних екстремумів запропоновано два алгоритми: з використанням IPOPT та модифікації r-алгоритму. Наводяться результати обчислювальних експериментів. |
| format |
Article |
| author |
Стецюк, П.І. Романова, Т.Є. Субота, І.О. |
| spellingShingle |
Стецюк, П.І. Романова, Т.Є. Субота, І.О. NLP-задача упаковки гомотетичних еліпсів у прямокутний контейнер Теорія оптимальних рішень |
| author_facet |
Стецюк, П.І. Романова, Т.Є. Субота, І.О. |
| author_sort |
Стецюк, П.І. |
| title |
NLP-задача упаковки гомотетичних еліпсів у прямокутний контейнер |
| title_short |
NLP-задача упаковки гомотетичних еліпсів у прямокутний контейнер |
| title_full |
NLP-задача упаковки гомотетичних еліпсів у прямокутний контейнер |
| title_fullStr |
NLP-задача упаковки гомотетичних еліпсів у прямокутний контейнер |
| title_full_unstemmed |
NLP-задача упаковки гомотетичних еліпсів у прямокутний контейнер |
| title_sort |
nlp-задача упаковки гомотетичних еліпсів у прямокутний контейнер |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2014 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/111521 |
| citation_txt |
NLP-задача упаковки гомотетичних еліпсів у прямокутний контейнер / П.І. Стецюк, Т.Є. Романова, І.О. Субота // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 139-146. — Бібліогр.: 12 назв. — укр. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT stecûkpí nlpzadačaupakovkigomotetičnihelípsívuprâmokutnijkontejner AT romanovatê nlpzadačaupakovkigomotetičnihelípsívuprâmokutnijkontejner AT subotaío nlpzadačaupakovkigomotetičnihelípsívuprâmokutnijkontejner |
| first_indexed |
2025-07-08T02:17:03Z |
| last_indexed |
2025-07-08T02:17:03Z |
| _version_ |
1837043311107375104 |
| fulltext |
Теорія оптимальних рішень. 2014 139
ТЕОРІЯ
ОПТИМАЛЬНИХ
РІШЕНЬ
Розглядається проблема упаковки
гомотетичних одинаково
орієнтованих еліпсів у
прямокутному контейнері
мінімальної площі (або
периметра). Наведено її
формулювання у вигляді
багатоекстремальної задачі
нелінійного програмування. Для
пошуку локальних екстремумів
запропоновано два алгоритми: з
використанням IPOPT та
модифікації r-алгоритму.
Наводяться результати
обчислювальних експериментів.
П.І. Стецюк, Т.Є. Романова,
І.О. Субота, 2014
УДК 519.8
П.І. СТЕЦЮК, Т.Є. РОМАНОВА, І.О. СУБОТА
NLP-ЗАДАЧА УПАКОВКИ
ГОМОТЕТИЧНИХ ЕЛІПСІВ
У ПРЯМОКУТНИЙ КОНТЕЙНЕР
Вступ. Задачі оптимального розміщення
еліпсів у контейнері мінімальних розмірів
відносяться до класу задач упаковки та
розкрою (Packing & Cutting, [1]), які мають
широкий спектр наукових та практичних
застосувань. Зокрема, задачі упаковки
еліпсів виникають у порошковій металургії,
молекулярній динаміці, мінеральній
промисловості та багатьох інших. Одне з
важливих застосувань – моделювання руху
сипучих речовин.
Тривалий час як математичні моделі
гранульованих матеріалів розглядалися круги.
Однак отримані у такий спосіб математичні
моделі суттєво відрізнялися від реальних
моделей. У роботах [2, 3] для розв’язання
задач даного типу застосовується метод
дискретного елемента. Цей метод є
поширеним інструментом для розв’язання
багатьох виробничих задач, однак він –
трудомісткий, що обмежує вимірність задачі
і кількість використовуваних частинок.
У роботах [4, 5] моделюється випадкова
упаковка еліпсоїдів і досліджується
щільність отриманої упаковки. Доведено, що
еліпсоїди можуть бути упаковані щільніше,
ніж кулі. При моделюванні випадкового
розміщення еліпсів у контейнері, досягнутий
максимальний коефіцієнт щільності 0,895
[6].
У даній роботі розглядаються алгоритми
розв'язання задачі оптимальної упаковки
гомотетичних однаково орієнтованих еліпсів
у контейнер прямокутної форми.
Робота підтримана спільним грантом НАНУ
та НТЦУ (проект № 5710).
П.І. СТЕЦЮК, Т.Є. РОМАНОВА, І.О. СУБОТА
140 Теорія оптимальних рішень. 2014
Постановка задачі та математична модель. Маємо сімейство
гомотетичних однаково орієнтованих еліпсів i , 1, ...,i n , які задані
довжинами великої і малої напівосей ia та ib . Таким чином, для кожної пари
еліпсів i та j справедливо співвідношення
ji
i j
aa
b b
, {1, .., }ni j I n .
Вважаємо, що початок власної системи координат еліпса i знаходиться в
центрі його симетрії.
Положення еліпса i у просторі 2 характеризується вектором трансляції
2( , )i i ix y , де 2 – арифметичний евклідів простір.
Контейнер визначається як прямокутна область 2{( , ) ,x y
, }A x A B y B змінної довжини A та змінної ширини B . Позначимо
( , )p A B вектор змінних контейнера .
Як цільова функція F розглядається напівпериметр контейнера –
F A B або площа контейнера – F A B .
Задача оптимальної упаковки еліпсів полягає у наступному. Сімейство
еліпсів i , 1, ...,i n , які не перетинаються, потрібно розмістити у контейнері
так, щоб цільова функція F досягала свого мінімального значення.
Нехай вектор змінних задачі має вигляд 1 2( , , , ..., )nu p 2 2n .
Математична модель задачі в термінах phi-функцій формулюється у вигляді [7]:
знайти
2 2
min ( ),
nu W
F u
(1)
де
2 2 *{ : ( ) 0, ( ) 0, 1, ..., , 1, ..., }n
iW u u u m i n
, (2)
а відповідні phi-функції мають наступний вигляд:
2 2
2 2
( ) ( )
1,
( ) ( )
i j i j
i j i j
x x y y
a a b b
i 1, ...,j n ,
* 1 2 3 4min{ , , , }i i i i i , 1,..., ,i n
де
1 ,i i ix A a 2 ,i i iy B b 3 ,i i ix A a 4
i i iy B b ,
а 0.5 ( 1)m n n визначає повну кількість функцій , які задають умови, що
еліпси не перетинаються.
Задача (1), (2) – багатоекстремальна задача нелінійного програмування, де
цільова функція або лінійна, або квадратична. Множина допустимих розв'язків
задається квадратичними та кусочно-лінійними функціями. Для пошуку
локальних екстремумів задачі (1), (2) розглянемо два алгоритми: перший
NLP-ЗАДАЧА УПАКОВКИ ГОМОТЕТИЧНИХ ЕЛІПСІВ У ПРЯМОКУТНИЙ КОНТЕЙНЕР
Теорія оптимальних рішень. 2014 141
використовує модифікацію r-алгоритму Шора, а другий – відому програму
IPOPT.
Алгоритм 1. Для напівперимера контейнера задачі оптимальної упаковки
еліпсів відповідає наступна задача нелінійного програмування:
знайти
*
, , ,
min ( )
x y A B
F A B , (3)
при обмеженнях
2 2
2 2
( ) ( )
1, 1 ,
( ) ( )
i j i j
i j i j
x x y y
i j n
a a b b
(4)
, , 1, ..., ,i i i iA x a x a A i n (5)
, , 1, ..., ,i i i iB y b y b B i n (6)
де 1 1( , ..., ), ( , ..., )n nx x x y y y .
За допомогою негладких штрафів задача (3) – (6) зводиться до задачі без-
умовної мінімізації негладкої функції
, , ,
min { ( , , , ) ( ) ( , , )}P
A B x y
f A B x y A B r x y , (7)
де штрафна негладка функція ( , , , )P A B x y має вигляд
1 1 2 2( , , , ) ( , ) ( , , , )P A B x y P F x y P F A B x y . (8)
Тут kP – додатні штрафні коефіцієнти, 1, 2,k а функції 1( , )F x y
та 2( , , , )F A B x y визначаються так:
2 21
1 2 2
1 1
( ) ( )
( , ) max{0, 1}
( ) ( )
n n
i j i j
i j i i j i j
x x y y
F x y
a a b b
,
2
1 1
( , , , ) max{0, } max{0, }
n n
i i i i
i i
F A B x y x A a y B b
1 1
max{0, } max{0, }
n n
i i i i
i i
x A a y B b
.
Використання в (8) штрафних коефіцієнтів kP , 1, 2k , дозволяє врахувати
більшу точність для виконання квадратичних обмежень (4) та меншу точність
для виконання лінійних обмежень (5), (6). Це дає можливість раціонально
керувати знаходженням близьких до граничних екстремальних точок із
множини допустимих розв'язків у задачі (3) – (6).
Алгоритм пошуку найкращого розв'язку задачі (3) – (6) полягає у
наступному. Для заданого набору стартових точок здійснюється пошук
локальних мінімумів в задачі (7) за допомогою модифікації r -алгоритму [8].
Найкращий із
П.І. СТЕЦЮК, Т.Є. РОМАНОВА, І.О. СУБОТА
142 Теорія оптимальних рішень. 2014
локальних мінімумів функції ( , , , )f A B x y , для якого штрафна функція
( , , , )P A B x y близька до нуля, приймається за ( , , , )r r r rA B x y – розв’язок
задачі (3) – (6). Йому відповідає найкраще (рекордне) значення цільової функції
r r rF A B – найменший напівпериметр прямокутника, який реалізується для
його довжини rA та його ширини .rB Стартові точки генеруються випадковим
чином у прямокутнику розмірів ( , )r rA B , які послідовно уточнюються за мірою
знаходження кращого локального мінімуму.
Програмна реалізація алгоритму виконана на некомерційній мові GNU
Octave [9]. Програма або знаходить один з локальних мінімумів у задачі
(1), (2), або повідомляє про неможливість знайти допустиму точку для системи
обмежень (2). Ядром програми є octave-функція ralgb5, яка реалізує r -алгоритм
з постійною величиною коефіцієнта розтягу простору та адаптивним
регулюванням кроку в напрямку нормованого антисубградієнта. Це
регулювання спрямоване на збільшення точності пошуку мінімуму функції за
напрямком у процесі обчислень. При цьому, як правило, гарантується, що
середнє (по ітераціях) число кроків не перевищує двох-трьох.
Для мінімальної площі контейнера алгоритм 1 буде аналогічним.
Алгоритм 2. Суть алгоритму полягає у побудові стартових точок і
використанні IPOPT для локальної оптимізації. Як локально-оптимальний
розв’язок вибирається найкращий із отриманих локальних екстремумів.
Алгоритм 2, використовує метод, запропонований у [10] для розміщення кіл у
смузі мінімальної довжини.
Виберемо розміри прямокутника 0 0,A A B B , які гарантують розміщення
еліпсів iE у прямокутнику 0. При цьому, не втрачаючи загальності,
вважаємо, що 1 2 1.... .n na a a a Розміщення еліпсів визначається
вектором трансляції ( , ).i i ix y Нехай коефіцієнти гомотетії i еліпсів iE ,
ni I , являються змінними і формують вектор 1( , ..., ) n
n . Тоді
3( , ) nu – вектор змінних.
Крок 1. Вибираємо точку 0(1) 0 0( , 0) ( , 0, ..., 0),u де
0 генерується
випадково, так що 0
0i , ni I .
Як стартову точку для подальшої оптимізації вибираємо
0(1)u і переходимо
до кроку 2.
Крок 2. Розв'язуємо задачу
3' 1
max
n
n
i i
u W i
a
, (9)
3 *' { : ( ) 0, ( ) 0, 1, ..., , 0 1, 1, ..., }.n
i iW u u u m i n (10)
NLP-ЗАДАЧА УПАКОВКИ ГОМОТЕТИЧНИХ ЕЛІПСІВ У ПРЯМОКУТНИЙ КОНТЕЙНЕР
Теорія оптимальних рішень. 2014 143
В результаті отримуємо точку глобального максимуму 0(2) 0(2) 0(2)( , )u v .
Як стартову точку для подальшої оптимізації вибираємо 0(2)u і переходимо
до кроку 3.
Крок 3. Знаходимо 0(3) 0(3) 0(3) 0(3)( , , )u A B v – точку локального мінімуму
задачі (1, 2).
Крок 4. Зменшуємо розміри еліпсів iE , 1, 2, ..., ,i n вважаючи коефіцієнти
гомотетії рівними 1i , 1, 2, ...,i n .
Як стартову точку для подальшої оптимізації вибираємо 0(3)u і переходимо
до кроку 3, розв'язуючи задачу (1), (2) для еліпсів з розмірами
i i ia a , i i ib b , 1, 2, ...,i n .
Отримуємо точку локального мінімуму
0(4) 0(4)0(4) 0(4)
( , , ).u A B v .
Крок 5. Як стартову точку для подальшої оптимізації вибираємо точку
0(4)
( , ),v де 1( , ..., )n для зафіксованих розмірів області
0(4)
,A A
0(4)
B B . Розв'язуємо задачу (9), (10) та отримуємо точку локального
максимуму 0(5) 0(5) 0(5)( , )u v .
Крок 6. Як стартову точку для подальшої оптимізації вибираємо точку
0(5) 0(5) 0(5)( , )u v для зафіксованих розмірів області
0(4) 0(4)
,A A B B та
розв'язуємо наступну задачу:
3
2
'' 1
max ( )
n
n
i i
u W i
a
, (11)
3'' { : ( ) 0, ( ) 0, 1, ..., , , 1, ..., }n
i i iW u u u m a a a i n
, (12)
min{ , 1, ..., }ia a i n , max{ , 1, ..., }ia a i n .
Отримуємо точку локального максимуму 0(6) 0(6) 0(6)( , )u v .
Крок 7. Ранжируємо за зменшенням
0(6)
i iia a , 1, ..., .i n Формуємо
послідовність 1 2 1( , , ...., , )n ni i i i , таку, що 1 2 1
.... .
n ni i i ia a a a
Здійснюємо порівняння ia і :
jia якщо
0(6)
1i , то вважаємо
0(7)
1
ji
,
якщо
0(6)
1i , то вважаємо
0(7) 0(6)
j
ii
. Формуємо точку 0(7) 0(7) 0(7)( , )u v
та переходимо до кроку (2). Стартуючи з точки
0(7)u , розв'язуємо задачу
П.І. СТЕЦЮК, Т.Є. РОМАНОВА, І.О. СУБОТА
144 Теорія оптимальних рішень. 2014
(9), (10). В результаті отримуємо точку глобального максимуму
0(2) 0(2) 0(2)( , )u v . Переходимо до кроку 3. Стартуючи з точки 0(2)u ,
розв'язуємо задачу (1), (2) та отримуємо точку локального мінімуму
* * * *( , , )u A B v .
Обчислювальні експерименти. В табл. 1 наведено результати
експериментів по знаходженню мінімального напівпериметра прямокутного
контейнера для десяти еліпсів, довжини осей яких наведено в колонках 2 та 3.
Розглядалися три варіанти розв'язання задачі (1), (2): варіант 1 означає, що
задача (1), (2) розв’язувалась за допомогою програми IPOPT [11, 12], стартуючи
з 50 випадкових точок; варіант 2 – для розв'язання задачі (7), (8)
використовувався алгоритм 1
з генерацією за його правилом 50 випадкових точок; варіант 3 – використову-
вався алгоритм 2, стартуючи з 50 випадкових точок (для локальної оптимізації
в задачах (1), (2), (9), (10), (11), (12) використовувалася програма IPOPT).
ТАБЛИЦЯ 1. Найкращі розміщення десяти еліпсів для трьох варіантів
№ ai bi
Варіант 1 Варіант 21 Варіант 3
xi* yi* xi* yi* xi* yi*
1 9 3 20.994 20.633 –20.999 29.253 21.000 –1.665
2 18 6 −11.933 25.246 11.999 –5.816 –10.680 –5.921
3 6 2 23.997 0.732 –23.999 –30.252 –24.000 –12.578
4 12 4 −18.000 −8.869 –17.999 22.324 –18.000 –8.856
5 30 10 0.000 −21.522 0.000 9.675 0.000 –21.523
6 9 3 −20.825 −1.417 –20.613 –10.168 21.000 20.634
7 18 6 10.673 −5.922 10.653 26.098 –12.000 25.193
8 6 2 23.998 −12.576 23.469 19.058 –24.000 0.7344
9 12 4 17.280 27.523 –17.618 –3.130 17.190 27.521
10 30 10 0.000 9.677 0,0000 –21.308 0.000 9.679
A* = 30.000
B* = 32.253
F* = 62.253
A* = 30.000
B* = 31.523
F* = 61.523
A* = 30.000
B* = 31.523
F* = 61.523
Найменше значення цільової функції F* = 61.523 отримано як за допомогою
алгоритму 1, так і за допомогою алгоритму 2. Отримані розв’язки відрізняються
тільки антисиметричним розміщенням еліпсів другого знизу шару, який
включає п’ять еліпсів (див. рисунок, варіант 2 та варіант 3). Для варіанта 1
коефіцієнт заповнення дорівнює 0.80359, а для варіанта 2 та варіанта 3 –
дорівнює 0.8222.
NLP-ЗАДАЧА УПАКОВКИ ГОМОТЕТИЧНИХ ЕЛІПСІВ У ПРЯМОКУТНИЙ КОНТЕЙНЕР
Теорія оптимальних рішень. 2014 145
(Варіант 1) ((Варіант 2) (Варіант 3)
РИСУНОК. Розміщення еліпсів, що відповідають трьом варіантам із табл. 1
У табл. 2 наведено координати розміщення 20 еліпсів, довжини осей яких
наведено в колонках
ia та
ib . Для цього прикладу довжина та ширина
контейнера дорівнюють A* = 22.7719 та В* = 20.3749. Їм відповідає
напівпериметр
F* = 43.1468 та коефіцієнт заповнення рівний 0.79343. Цей локально
оптимальний розв’язок отримано за допомогою алгоритму 2.
ТАБЛИЦЯ 2. Параметри розміщення 20 еліпсів, що відповідають найкращому,
отриманому алгоритмом 2, локально оптимальному розв’язку
№ ai bi xi* yi* № ai bi xi* yi*
1 10.5 3.5 –12.2720 –11.9589 11 8.25 2.75 14.5220 2.0637
2 10.5 3.5 –12.2720 9.8688 12 8.25 2.75 14.5220 –13.6846
3 10.5 3.5 5.4661 –8.2119 13 7.5 2.5 13.3586 17.8750
4 10.5 3.5 11.9955 8.2567 14 7.5 2.5 –15.0125 0.0595
5 9.0 3.0 –13.7720 –5.4782 15 7.5 2.5 –15.2720 –17.8750
6 9.0 3.0 1.1984 –17.3552 16 7.5 2.5 15.2720 –3.1804
7 9.0 3.0 –13.7720 16.3495 17 6.0 2.0 16.7720 –18.3750
8 9.0 3.0 –1.9903 3.7272 18 6.0 2.0 –0.0578 18.3750
9 8.25 2.75 2.5325 13.7041 19 6.0 2.0 –16.7720 4.5773
10 8.25 2.75 –0.0657 –1.9869 20 6.0 2.0 16.7720 13.5212
Висновок. Математична модель задачі оптимальної упаковки гомотетичних
однаково орієнтованих еліпсів у прямокутний контейнер представлена як
багатоекстремальна задача нелінійного програмування. Для пошуку її
локальних екстремумів запропоновано два алгоритми. Перший використовує r -
алгоритм Шора в сполученні із процедурою мультистарту. Другий алгоритм
використовує відому програму IPOPT та спеціальний спосіб побудови стартових
точок. Ефективність алгоритмів підтверджується розрахунками для тестових
задач, де знайдено розміщення еліпсів з досить щільною їх упаковкою.
П.І. СТЕЦЮК, Т.Є. РОМАНОВА, І.О. СУБОТА
146 Теорія оптимальних рішень. 2014
Розглянуті у роботі алгоритми для задачі оптимальної упаковки
гомотетичних однаково орієнтованих еліпсів можуть бути застосовані для
розробки ефективних методів розв'язання задач розміщення еліпсів, які
допускають неперервні повороти.
П.И. Стецюк, Т.Е. Романова, И.А. Суббота
NLP-ЗАДАЧА УПАКОВКИ ГОМОТЕТИЧНЫХ ЭЛЛИПСОВ В ПРЯМОУГОЛЬНЫЙ
КОНТЕЙНЕР
Рассматривается проблема упаковки гомотетичных одинаково ориентированных эллипсов
в прямоугольном контейнере минимальной площади (или периметра). Дана ее формулировка
в виде многоэкстремальной задачи нелинейного программирования. Для поиска локальных
экстремумов предлагаются два алгоритма: с использованием IPOPT и модификации
r-алгоритма. Приводятся результаты вычислительных экспериментов.
P.І. Stetsyuk, Т.Е. Romanova, I.A. Subota
NLP-PROBLEM OF PACKING HOMOTHETIC ELLIPSES INTO
A RECTANGULAR CONTEINER
The paper considers a packing problem of a finite set of homothetic ellipses into a rectangular
container of the minimal perimeter (area). We formulate the problem in the form of a multiextremal
nonlinear programming one. In order to search for local extrema of the problem we propose two
algorithms. One algorithm uses IPOPT and the other algorithm based on a modification of the
r-algorithm. The results of computational experiments are given.
1. Wаscher G., Hauner H., Schumann H. An improved typology of cutting and packing problems
// European Journal of Operational Research. – 2007. – 183 (3). – P. 1109 – 1130.
2. Ting J., Khwaja M., Meachum L., Rowell J. An ellipse–based discrete element model for
granular materials // Numerical and Analytical Methods in Geomechanics. – 1993.– 17 (9). –
P. 603 – 623.
3. Feng Y., Han K. and Owen D. An Advancing Front Packing of Polygons, Ellipses and Spheres
// Discrete Element Methods. – 2002. – P. 93 – 98.
4. Donev A., Cisse I., Sachs D., Variano E.A., Stillinger F.H, Connelly R., Torquato S.,
Chaikin P.M. Improving the density of jammed disordered packings using ellipsoids // Science.
– 2004. – 303(5660). – P. 990 – 993.
5. Man W., Donev A., Stillinger F., Sullivan M., Russel W., Heeger D., Inati S., Torquato S.,
Chaikin P.M. Experiments on random packings of ellipsoids // Phys. Rev. Lett. – 2005.
– 94 (19).
6. Delaney G., Weaire D., Hutzler S., Murphy S. Random packing of elliptical disks //
Philosophical Magazine Letters. – 2005. – 85(2). – P. 89 – 96.
7. Романова Т.Е., Суббота И.А., Стецюк П.И. Задача упаковки гомотетичных эллипсов в
прямоугольном контейнере минимальных размеров // Математическое моделирование,
оптимизация и информационные технологии: материалы 4-й Междунар. науч. конф.
(Кишинэу, 25 – 28 марта 2014). – Кишинэу: Эврика, 2014. – С. 396 – 405.
8. Шор Н.З., Стецюк П.И. Использование модификации r -алгоритма для нахождения
глобального минимума полиномиальных функций // Кибернетика и системный анализ. –
1997. – № 4. – C. 28 – 49.
NLP-ЗАДАЧА УПАКОВКИ ГОМОТЕТИЧНИХ ЕЛІПСІВ У ПРЯМОКУТНИЙ КОНТЕЙНЕР
Теорія оптимальних рішень. 2014 147
9. Octave [Электронный ресурс]: http://www.octave.org. – Режим доступа: свободный.
10. Стоян Ю.Г., Яськов Г.Н. Переход от одного локального минимума к другому в задаче
упаковки неравных кругов в полосе минимальной длины // Доп. НАН України. – 2013. –
№ 5. – C. 44 – 50.
11. Wachter A., Biegler L. On the implementation of an interior-point filter line-search algorithm
for large-scale nonlinear programming // Mathematical Programming. – 2006. – 106(1). –
P. 25 – 57.
12. IPOPT [Электронный ресурс]: https://projects.coin-or.org/Ipopt.
Одержано 07.04.2014
http://www.octave.org/
https://projects.coin-or.org/Ipopt
|