Packing convex homothetic polytopes into a cuboid
This paper deals with the optimization problem of packing a given set of homothetical arbitrarily oriented convex polytopes without their overlapping in a linear parallelepiped of minimal volume. Phi-functions are proposed to be used as a constructive means of the mathematical modeling of a given pr...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English Ukrainian |
| Опубліковано: |
Інститут енергетичних машин і систем ім. А. М. Підгорного Національної академії наук України
2018
|
| Теми: | |
| Онлайн доступ: | https://journals.uran.ua/jme/article/view/135431 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Energy Technologies & Resource Saving |
Репозитарії
Energy Technologies & Resource Saving| id |
oai:ojs.journals.uran.ua:article-135431 |
|---|---|
| record_format |
ojs |
| institution |
Energy Technologies & Resource Saving |
| collection |
OJS |
| language |
English Ukrainian |
| topic |
packing homothetic polytopes rotations optimization phi-functions UDC 519.85 упаковка гомотетичные многогранники вращение оптимизация Ф-функции УДК 519.85 пакування гомотетичні багатогранники обертання оптимізація Ф-функції УДК 519.85 |
| spellingShingle |
packing homothetic polytopes rotations optimization phi-functions UDC 519.85 упаковка гомотетичные многогранники вращение оптимизация Ф-функции УДК 519.85 пакування гомотетичні багатогранники обертання оптимізація Ф-функції УДК 519.85 Stoyan, Yu. G. Chugay, A. M. Packing convex homothetic polytopes into a cuboid |
| topic_facet |
packing homothetic polytopes rotations optimization phi-functions UDC 519.85 упаковка гомотетичные многогранники вращение оптимизация Ф-функции УДК 519.85 пакування гомотетичні багатогранники обертання оптимізація Ф-функції УДК 519.85 |
| format |
Article |
| author |
Stoyan, Yu. G. Chugay, A. M. |
| author_facet |
Stoyan, Yu. G. Chugay, A. M. |
| author_sort |
Stoyan, Yu. G. |
| title |
Packing convex homothetic polytopes into a cuboid |
| title_short |
Packing convex homothetic polytopes into a cuboid |
| title_full |
Packing convex homothetic polytopes into a cuboid |
| title_fullStr |
Packing convex homothetic polytopes into a cuboid |
| title_full_unstemmed |
Packing convex homothetic polytopes into a cuboid |
| title_sort |
packing convex homothetic polytopes into a cuboid |
| title_alt |
Упаковка выпуклых гомотетичних многогранников в кубоид Упакування опуклих гомотетичних багатогранників в кубоїд |
| description |
This paper deals with the optimization problem of packing a given set of homothetical arbitrarily oriented convex polytopes without their overlapping in a linear parallelepiped of minimal volume. Phi-functions are proposed to be used as a constructive means of the mathematical modeling of a given problem. On the basis of the phi-function a mathematical model of the problem is constructed for two convex non-oriented polytopes, and its main properties which influence the choice of the strategy for solving the problem are examined. The obtained mathematical model presents the problem in the form of a classical problem of nonlinear programming, which makes it possible to use modern solvers for searching for a solution. Effective methods for finding valid starting points and locally optimal solutions based on homothetic transformations are proposed. To search for local extrema of the formulated optimization problems, a special method of decomposition has been developed, which allows us to significantly reduce computational costs due to a considerable reduction in the number of inequalities. The key idea of the optimization procedure allows us to generate subsets of the domain of admissible solutions at each stage of searching for a local extremum. Parallel computations were used to search for local extrema, which made it possible to reduce time expenditures. Numerical examples are given. The methods proposed in the work can be used for solving the problem of packaging convex polytopes. |
| publisher |
Інститут енергетичних машин і систем ім. А. М. Підгорного Національної академії наук України |
| publishDate |
2018 |
| url |
https://journals.uran.ua/jme/article/view/135431 |
| work_keys_str_mv |
AT stoyanyug packingconvexhomotheticpolytopesintoacuboid AT chugayam packingconvexhomotheticpolytopesintoacuboid AT stoyanyug upakovkavypuklyhgomotetičnihmnogogrannikovvkuboid AT chugayam upakovkavypuklyhgomotetičnihmnogogrannikovvkuboid AT stoyanyug upakuvannâopuklihgomotetičnihbagatogrannikívvkuboíd AT chugayam upakuvannâopuklihgomotetičnihbagatogrannikívvkuboíd |
| first_indexed |
2024-09-01T17:37:00Z |
| last_indexed |
2024-09-01T17:37:00Z |
| _version_ |
1809016129161527296 |
| spelling |
oai:ojs.journals.uran.ua:article-1354312018-07-02T09:20:09Z Packing convex homothetic polytopes into a cuboid Упаковка выпуклых гомотетичних многогранников в кубоид Упакування опуклих гомотетичних багатогранників в кубоїд Stoyan, Yu. G. Chugay, A. M. packing homothetic polytopes rotations optimization phi-functions UDC 519.85 упаковка гомотетичные многогранники вращение оптимизация Ф-функции УДК 519.85 пакування гомотетичні багатогранники обертання оптимізація Ф-функції УДК 519.85 This paper deals with the optimization problem of packing a given set of homothetical arbitrarily oriented convex polytopes without their overlapping in a linear parallelepiped of minimal volume. Phi-functions are proposed to be used as a constructive means of the mathematical modeling of a given problem. On the basis of the phi-function a mathematical model of the problem is constructed for two convex non-oriented polytopes, and its main properties which influence the choice of the strategy for solving the problem are examined. The obtained mathematical model presents the problem in the form of a classical problem of nonlinear programming, which makes it possible to use modern solvers for searching for a solution. Effective methods for finding valid starting points and locally optimal solutions based on homothetic transformations are proposed. To search for local extrema of the formulated optimization problems, a special method of decomposition has been developed, which allows us to significantly reduce computational costs due to a considerable reduction in the number of inequalities. The key idea of the optimization procedure allows us to generate subsets of the domain of admissible solutions at each stage of searching for a local extremum. Parallel computations were used to search for local extrema, which made it possible to reduce time expenditures. Numerical examples are given. The methods proposed in the work can be used for solving the problem of packaging convex polytopes. В работе рассматривается оптимизационная задача упаковки заданного набора гомотетичних произвольно ориентированных выпуклых многогранников без их взаимного пересечения в прямом параллелепипеде минимального объема. Как конструктивные средства математического моделирования поставленной задачи предлагается использовать метод Ф-функции. На основе Ф-функции для двух выпуклых неориентированных многогранников строится математическая модель задачи, и исследуются ее основные свойства, которые влияют на выбор стратегии решения поставленной задачи. Полученная математическая модель представляет задачу в виде классической задачи нелинейного программирования, что позволяет использовать для поиска решения современные Солверы. Предлагаются методы поиска допустимых начальных точек и локально оптимальных решений, основанные на гомотетичных преобразованиях. Для поиска локальных экстремумов сформулированных оптимизационных задач разработан специальный метод декомпозиции, который позволяет значительно уменьшить вычислительные затраты за счет значительного уменьшения количества неравенств. Ключевая идея процедуры оптимизации позволяет генерировать подмножества области допустимых решений на каждом этапе поиска локального экстремума. Для поиска локальных экстремумов использовались параллельные вычисления, что позволило сократить временные затраты. Приведены числовые примеры. Предложенные в работе методы могут быть использованы для решения задачи упаковки невыпуклых многогранников. У роботі розглядається оптимізаційна задача упакування заданого набору гомотетичних довільно орієнтованих опуклих багатогранників без їх взаємного перетинання у прямому паралелепіпеді мінімального об'єму. Як конструктивні засоби математичного моделювання поставленої задачі пропонується використовувати метод Ф-функції. На основі Ф-функції для двох опуклих неорієнтованих багатогранників будується математична модель задачі та досліджуються її основні властивості, які впливають на вибір стратегії розв’язання поставленої задачі. Отримана математична модель подає задачу у вигляді класичної задачі нелінійного програмування, що дозволяє використовувати для пошуку розв’язку сучасні солвери. Пропонуються ефективні методи пошуку припустимих початкових точок і локально оптимальних розв'язків, що ґрунтуються на гомотетичних перетвореннях. Для пошуку локальних екстремумів сформульованих оптимізаційних задач розроблено спеціальний метод декомпозиції, який дозволяє значно зменшити обчислювальні витрати за рахунок значного зменшення кількості нерівностей. Ключова ідея процедури оптимізації дозволяє генерувати підмножини області припустимих розв'язків на кожному етапі пошуку локального екстремуму. Для пошуку локальних екстремумів використовувались паралельні обчислення, що дозволило скоротити часові витрати. Наведено числові приклади. Запропоновані в роботі методи можуть бути використані для розв’язання задачі упакування неопуклих багатогранників. Інститут енергетичних машин і систем ім. А. М. Підгорного Національної академії наук України 2018-06-26 Article Article application/pdf application/pdf https://journals.uran.ua/jme/article/view/135431 Journal of Mechanical Engineering; Vol. 21 No. 2 (2018); 45-59 Проблемы машиностроения; Том 21 № 2 (2018); 45-59 Проблеми машинобудування; Том 21 № 2 (2018); 45-59 2709-2992 2709-2984 en uk https://journals.uran.ua/jme/article/view/135431/132323 https://journals.uran.ua/jme/article/view/135431/132530 Copyright (c) 2018 Yu. G. Stoyan, A. M. Chugay https://creativecommons.org/licenses/by-nd/4.0 |