Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери

Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери

The article considers mathematical models and algorithms for optimal balancedsparse packing of spheres and cubes into spherical and cubic containers. A balanced sparse (allowable distances between objects are specified) packing of objects into an outer container is such a packing that the center of...

Full description

Saved in:
Bibliographic Details
Date:2023
Main Authors: Stetsyuk, Petro, Berezovskyi, Oleg, Lykhovyd, Oleksii, Stetsyuk, Mariia
Format: Article
Language:Ukrainian
Published: V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2023
Subjects:
задачі упаковки
розрідженість упаковки
негладка оптимізація
квадратичні екстремальні задачі
паралельні алгоритми
високопродуктивні обчислення
Online Access:https://jais.net.ua/index.php/files/article/view/59
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Problems of Control and Informatics

Institution

Problems of Control and Informatics
id oai:ojs2.jais.net.ua:article-59
record_format ojs
institution Problems of Control and Informatics
baseUrl_str
datestamp_date 2024-03-13T13:07:21Z
collection OJS
language Ukrainian
topic задачі упаковки
розрідженість упаковки
негладка оптимізація
квадратичні екстремальні задачі
паралельні алгоритми
високопродуктивні обчислення
spellingShingle задачі упаковки
розрідженість упаковки
негладка оптимізація
квадратичні екстремальні задачі
паралельні алгоритми
високопродуктивні обчислення
Stetsyuk, Petro
Berezovskyi, Oleg
Lykhovyd, Oleksii
Stetsyuk, Mariia
Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери
topic_facet packing problems
packing sparsity
non-smooth optimization
quadratic extremal problems
parallel algorithms
high-performance computing
задачи упаковки
разреженность упаковки
негладкая оптимизация
квадратические экстремальные задачи
параллельные алгоритмы
высокопроизводительные вычисления
задачі упаковки
розрідженість упаковки
негладка оптимізація
квадратичні екстремальні задачі
паралельні алгоритми
високопродуктивні обчислення
format Article
author Stetsyuk, Petro
Berezovskyi, Oleg
Lykhovyd, Oleksii
Stetsyuk, Mariia
author_facet Stetsyuk, Petro
Berezovskyi, Oleg
Lykhovyd, Oleksii
Stetsyuk, Mariia
author_sort Stetsyuk, Petro
title Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери
title_short Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери
title_full Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери
title_fullStr Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери
title_full_unstemmed Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери
title_sort математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери
title_alt Mathematical models and algorithms for optimal packing of balls and cubes into spherical and cubic containers
Математические модели и алгоритмы оптимальной упаковки шаров и кубов в сферический и кубический контейнеры
description The article considers mathematical models and algorithms for optimal balancedsparse packing of spheres and cubes into spherical and cubic containers. A balanced sparse (allowable distances between objects are specified) packing of objects into an outer container is such a packing that the center of gravity of thefamily of objects coincides with the center of the outer container, and the distances between the objects as well as the distances from them to the outer container are not less than the predetermined values. Mathematical models, sequential and parallel algorithms for solving problems of finding a balanced sparsepacking of balls of different radii into spherical and cubic containers are given.A mathematical model of the problem of finding a balanced sparse packing ofcubes into a cube of minimum volume, provided that the sides of all cubes areparallel to the coordinate axes, and a description of the non-smooth penaltyfunction for finding local minima of the problem are given. The investigatedproblems belong to the class of NP-hard problems. Mathematical models arerepresented by multi-extremal nonlinear programming problems. To find thebest feasible solution, the multistart method is used in combination with Shor's ralgorithm. For this, the problem is reduced to the unconditional optimizationproblem using penalty functions in the form of maximum functions, and nonsmooth optimization methods based on the use of software implementations of ralgorithm are used to find local minima from a set of starting points. Mathematical models and sequential and parallel algorithms under consideration can beused to develop software tools for solving problems of finding a balanced sparsepacking of spherical and cubic objects into spherical and cubic containers. Thematerial is presented in three sections. The first section presents a mathematicalmodel and algorithms for solving the problem of finding a balanced sparse packing of balls of different radii into a spherical container. The sequential and parallel algorithms for finding the best feasible problem solution are described. Section 2 provides a mathematical model and algorithms for solving the problem offinding a balanced sparse packing of balls of different radii into a cubic container. The sequential and parallel algorithms for finding the best feasible problemsolution are described. Section 3 presents a mathematical model of the problemof finding a balanced sparse packing of cubes into a cubic container. A description ofthe non-smooth penalty function for finding local minima of the problem is given.
publisher V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
publishDate 2023
url https://jais.net.ua/index.php/files/article/view/59
work_keys_str_mv AT stetsyukpetro mathematicalmodelsandalgorithmsforoptimalpackingofballsandcubesintosphericalandcubiccontainers
AT berezovskyioleg mathematicalmodelsandalgorithmsforoptimalpackingofballsandcubesintosphericalandcubiccontainers
AT lykhovydoleksii mathematicalmodelsandalgorithmsforoptimalpackingofballsandcubesintosphericalandcubiccontainers
AT stetsyukmariia mathematicalmodelsandalgorithmsforoptimalpackingofballsandcubesintosphericalandcubiccontainers
AT stetsyukpetro matematičeskiemodeliialgoritmyoptimalʹnojupakovkišarovikubovvsferičeskijikubičeskijkontejnery
AT berezovskyioleg matematičeskiemodeliialgoritmyoptimalʹnojupakovkišarovikubovvsferičeskijikubičeskijkontejnery
AT lykhovydoleksii matematičeskiemodeliialgoritmyoptimalʹnojupakovkišarovikubovvsferičeskijikubičeskijkontejnery
AT stetsyukmariia matematičeskiemodeliialgoritmyoptimalʹnojupakovkišarovikubovvsferičeskijikubičeskijkontejnery
AT stetsyukpetro matematičnímodelítaalgoritmioptimalʹnoíupakovkikulʹtakubívusferičnijtakubíčnijkontejneri
AT berezovskyioleg matematičnímodelítaalgoritmioptimalʹnoíupakovkikulʹtakubívusferičnijtakubíčnijkontejneri
AT lykhovydoleksii matematičnímodelítaalgoritmioptimalʹnoíupakovkikulʹtakubívusferičnijtakubíčnijkontejneri
AT stetsyukmariia matematičnímodelítaalgoritmioptimalʹnoíupakovkikulʹtakubívusferičnijtakubíčnijkontejneri
first_indexed 2025-10-30T02:48:34Z
last_indexed 2025-10-30T02:48:34Z
_version_ 1847373347471491072
spelling oai:ojs2.jais.net.ua:article-592024-03-13T13:07:21Z Mathematical models and algorithms for optimal packing of balls and cubes into spherical and cubic containers Математические модели и алгоритмы оптимальной упаковки шаров и кубов в сферический и кубический контейнеры Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери Stetsyuk, Petro Berezovskyi, Oleg Lykhovyd, Oleksii Stetsyuk, Mariia packing problems packing sparsity non-smooth optimization quadratic extremal problems parallel algorithms high-performance computing задачи упаковки разреженность упаковки негладкая оптимизация квадратические экстремальные задачи параллельные алгоритмы высокопроизводительные вычисления задачі упаковки розрідженість упаковки негладка оптимізація квадратичні екстремальні задачі паралельні алгоритми високопродуктивні обчислення The article considers mathematical models and algorithms for optimal balancedsparse packing of spheres and cubes into spherical and cubic containers. A balanced sparse (allowable distances between objects are specified) packing of objects into an outer container is such a packing that the center of gravity of thefamily of objects coincides with the center of the outer container, and the distances between the objects as well as the distances from them to the outer container are not less than the predetermined values. Mathematical models, sequential and parallel algorithms for solving problems of finding a balanced sparsepacking of balls of different radii into spherical and cubic containers are given.A mathematical model of the problem of finding a balanced sparse packing ofcubes into a cube of minimum volume, provided that the sides of all cubes areparallel to the coordinate axes, and a description of the non-smooth penaltyfunction for finding local minima of the problem are given. The investigatedproblems belong to the class of NP-hard problems. Mathematical models arerepresented by multi-extremal nonlinear programming problems. To find thebest feasible solution, the multistart method is used in combination with Shor's ralgorithm. For this, the problem is reduced to the unconditional optimizationproblem using penalty functions in the form of maximum functions, and nonsmooth optimization methods based on the use of software implementations of ralgorithm are used to find local minima from a set of starting points. Mathematical models and sequential and parallel algorithms under consideration can beused to develop software tools for solving problems of finding a balanced sparsepacking of spherical and cubic objects into spherical and cubic containers. Thematerial is presented in three sections. The first section presents a mathematicalmodel and algorithms for solving the problem of finding a balanced sparse packing of balls of different radii into a spherical container. The sequential and parallel algorithms for finding the best feasible problem solution are described. Section 2 provides a mathematical model and algorithms for solving the problem offinding a balanced sparse packing of balls of different radii into a cubic container. The sequential and parallel algorithms for finding the best feasible problemsolution are described. Section 3 presents a mathematical model of the problemof finding a balanced sparse packing of cubes into a cubic container. A description ofthe non-smooth penalty function for finding local minima of the problem is given. Рассмотрены математические модели и алгоритмы оптимальной сбалансированной разреженной упаковки шаров и кубов в сферический и кубический контейнеры. а расстояния между объектами и расстояния от них до внешнего контейнера были не меньше заданных величин. Приведены математические модели, последовательные и параллельные алгоритмы решения задач нахождения сбалансированной разреженной упаковки шаров разных радиусов в сферический и кубический контейнеры. Приведена математическая модель задачи нахождения сбалансированной разреженной упаковки кубов в куб минимального объема при условии, что стороны всех кубов параллельны осям координат и описание негладкой штрафной функции для поиска локальных минимумов задачи. Исследуемые задачи относятся к классу NP-трудных задач. Математические модели представлены многоэкстремальными задачами нелинейного программирования. Для поиска наилучшего допустимого решения применяется метод мультистарта в сочетании с r-алгоритмом Шора. Для этого задача сводится к задаче безусловной оптимизации с помощью штрафных функций в виде функций максимума, а для поиска локальных минимумов из набора стартовых точек применяются методы минимизации негладких функций, базирующихся на использовании программных реализаций r-алгоритма. Математические модели и последовательные и параллельные рассматриваемые алгоритмы можно использовать для разработки программных средств решения задач нахождения сбалансированной разреженной упаковки сферических и кубических объектов в сферические и кубические контейнеры. Материал представлен в трех разделах. В разд. 1 приведены математическая модель и алгоритмы решения задачи нахождения сбалансированной разреженной упаковки шаров разных радиусов в сферический контейнер. Описаны последовательные и параллельные алгоритмы нахождения лучшего допустимого решения задач. В разд. 2 приведены математическая модель и алгоритмы решения задачи нахождения сбалансированной разреженной упаковки шаров разных радиусов в кубический контейнер. Описан последовательный и параллельный алгоритмы нахождения наилучшего допустимого решения задач. В разд. 3 приведена математическая модель задачи нахождения сбалансированной разреженной упаковки кубов в кубический контейнер. Приведено описание гладкой штрафной функции для поиска локальных минимумов задачи. Розглянуто математичні моделі та алгоритми оптимальної збалансованоїрозрідженої упаковки куль та кубів у сферичний та кубічний контейнери.Збалансованою розрідженою (задаються допустимі відстані між обʼєктами)упаковкою об’єктів у зовнішній контейнер є така їх упаковка, коли центрваги сімейства об’єктів збігається з центром зовнішнього контейнера, авідстані між об’єктами та відстані від них до зовнішнього контейнера булине менші за наперед задані величини. Наведено математичні моделі, послідовні та паралельні алгоритми розв’язання задач знаходження збалансованої розрідженої упаковки куль різних радіусів у сферичний та кубічнийконтейнери. Наведено математичну модель задачі знаходження збалансованої розрідженої упаковки кубів у куб мінімального обʼєму за умови, щосторони всіх кубів паралельні осям координат, та опис негладкої штрафноїфункції для пошуку локальних мінімумів задачі. Досліджувані задачівідносяться до класу NP-важких задач. Математичні моделі представленібагатоекстремальними задачами нелінійного програмування. Для пошукунайкращого допустимого розвʼязку застосовується метод мультистарту усполученні з r-алгоритмом Шора. Для цього задача зводиться до задачібезумовної оптимізації за допомогою штрафних функцій у вигляді функціймаксимуму, а для пошуку локальних мінімумів із набору стартових точокзастосовуються методи мінімізації негладких функцій, що базуються навикористанні програмних реалізацій r-алгоритму. Математичні моделі тапослідовні і паралельні алгоритми, що розглядаються, можна використатидля розробки програмних засобів розв’язування задач знаходження збалансованої розрідженої упаковки сферичних та кубічних обʼєктів у сферичніта кубічні контейнери. Матеріал представлено в трьох розділах. У розд. 1 наведено математичну модель та алгоритми розв’язання задачі знаходження збалансованої розрідженої упаковки куль різних радіусів у сферичнийконтейнер. Описано послідовний та паралельний алгоритми знаходженнянайкращого допустимого розв’язку задач. У розд. 2 наведено математичну модель та алгоритми розв’язання задачі знаходження збалансованої розрідженоїупаковки куль різних радіусів у кубічний контейнер. Описано послідовний тапаралельний алгоритми знаходження найкращого допустимого розв’язкузадач. У розд. 3 наведено математичну модель задачі знаходження збалансованої розрідженої упаковки кубів у кубічний контейнер. Наведено описнегладкої штрафної функції для пошуку локальних мінімумів задачі. V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2023-07-07 Article Article application/pdf https://jais.net.ua/index.php/files/article/view/59 10.34229/2786-6505-2022-3-7 Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; Том 67 № 3 (2022): Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; 87-100 International Scientific Technical Journal "Problems of Control and Informatics; Том 67 № 3 (2022): International Scientific Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 87-100 International Scientific Technical Journal "Problems of Control and Informatics"; Vol. 67 No. 3 (2022): International Scientific Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 87-100 2786-6505 2786-6491 10.34229/2786-6505-2022-3 uk https://jais.net.ua/index.php/files/article/view/59/126 Copyright (c) 2022 Petro Stetsyuk , Oleg Berezovskyi, Oleksii Lykhovyd, Mariia Stetsyuk https://creativecommons.org/licenses/by-nc-nd/4.0/

Similar Items