Decomposition Algorithm for Optimization Placement Problems
The paper considers a placement problem of 2D convex objects in a rectangular domain of minimum area, that related to the field of Packing and Cutting problems. Our objects may be continuously translated and rotated. A nonlinear programming model of the problem is derived using the phi-function tech...
Saved in:
| Published in: | Математичне та комп'ютерне моделювання. Серія: Технічні науки |
|---|---|
| Date: | 2019 |
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/168582 |
| 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: | Decomposition Algorithm for Optimization Placement Problems / A. Pankratov, T. Romanova // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 19. — С. 126-131. — Бібліогр.: 6 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862560086889594880 |
|---|---|
| author | Pankratov, A. Romanova, T. |
| author_facet | Pankratov, A. Romanova, T. |
| citation_txt | Decomposition Algorithm for Optimization Placement Problems / A. Pankratov, T. Romanova // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 19. — С. 126-131. — Бібліогр.: 6 назв. — англ. |
| collection | DSpace DC |
| container_title | Математичне та комп'ютерне моделювання. Серія: Технічні науки |
| description | The paper considers a placement problem of 2D convex objects in a rectangular domain of minimum area, that related to the field of Packing and Cutting problems. Our objects may be continuously translated and rotated. A nonlinear programming model of the problem is derived using the phi-function technique. We develop an efficient decomposition algorithm to search for local optimal solutions for the placement problem. The algorithm reduces our problem to a sequence of nonlinear programming subproblems of considerably smaller dimension and a smaller number of nonlinear inequalities. The benefit of this approach is borne out by the computational results.
У статті розглядається задача розміщення двовимірних опуклих об'єктів у прямокутній області мінімальної площі, яка відноситься до класу задач упаковки і розкрою. Об'єкти, що розміщуються, можуть неперервно транслюватися і обертатися. Будується математична модель задачі розміщення у вигляді задачі нелінійного програмування з використанням методу phi-функцій. Для пошуку локально-оптимальних розв’язків пропонується ефективний алгоритм декомпозиції, який зводить вихідну задачу до послідовності підзадач нелінійного програмування значно меншою розмірності з меншим числом нелінійних нерівностей. Перевага цього підходу підтверджується результатами численних експериментів.
|
| first_indexed | 2025-11-25T22:57:35Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-168582 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 2308-5916 |
| language | Ukrainian |
| last_indexed | 2025-11-25T22:57:35Z |
| publishDate | 2019 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Pankratov, A. Romanova, T. 2020-05-04T17:14:49Z 2020-05-04T17:14:49Z 2019 Decomposition Algorithm for Optimization Placement Problems / A. Pankratov, T. Romanova // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 19. — С. 126-131. — Бібліогр.: 6 назв. — англ. 2308-5916 DOI: 10.32626/2308-5916.2019-19.126-131 https://nasplib.isofts.kiev.ua/handle/123456789/168582 519.859 The paper considers a placement problem of 2D convex objects in a rectangular domain of minimum area, that related to the field of Packing and Cutting problems. Our objects may be continuously translated and rotated. A nonlinear programming model of the problem is derived using the phi-function technique. We develop an efficient decomposition algorithm to search for local optimal solutions for the placement problem. The algorithm reduces our problem to a sequence of nonlinear programming subproblems of considerably smaller dimension and a smaller number of nonlinear inequalities. The benefit of this approach is borne out by the computational results. У статті розглядається задача розміщення двовимірних опуклих об'єктів у прямокутній області мінімальної площі, яка відноситься до класу задач упаковки і розкрою. Об'єкти, що розміщуються, можуть неперервно транслюватися і обертатися. Будується математична модель задачі розміщення у вигляді задачі нелінійного програмування з використанням методу phi-функцій. Для пошуку локально-оптимальних розв’язків пропонується ефективний алгоритм декомпозиції, який зводить вихідну задачу до послідовності підзадач нелінійного програмування значно меншою розмірності з меншим числом нелінійних нерівностей. Перевага цього підходу підтверджується результатами численних експериментів. uk Інститут кібернетики ім. В.М. Глушкова НАН України Математичне та комп'ютерне моделювання. Серія: Технічні науки Decomposition Algorithm for Optimization Placement Problems Алгоритм декомпозиції для розв’язання оптимізаційних задач розміщення Article published earlier |
| spellingShingle | Decomposition Algorithm for Optimization Placement Problems Pankratov, A. Romanova, T. |
| title | Decomposition Algorithm for Optimization Placement Problems |
| title_alt | Алгоритм декомпозиції для розв’язання оптимізаційних задач розміщення |
| title_full | Decomposition Algorithm for Optimization Placement Problems |
| title_fullStr | Decomposition Algorithm for Optimization Placement Problems |
| title_full_unstemmed | Decomposition Algorithm for Optimization Placement Problems |
| title_short | Decomposition Algorithm for Optimization Placement Problems |
| title_sort | decomposition algorithm for optimization placement problems |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/168582 |
| work_keys_str_mv | AT pankratova decompositionalgorithmforoptimizationplacementproblems AT romanovat decompositionalgorithmforoptimizationplacementproblems AT pankratova algoritmdekompozicíídlârozvâzannâoptimízacíinihzadačrozmíŝennâ AT romanovat algoritmdekompozicíídlârozvâzannâoptimízacíinihzadačrozmíŝennâ |