Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж
Розглянуто математичні моделі двох класів задач модернізації пропускних здатностей дуг відмовостійких орієнтованих мереж. Відмовостійкою вважається мережа, для якої можна задовольнити всі вимоги на передачу потоків, якщо матиме місце одна, будь-яка відмова, з усіх можливих одиничних відмов мережі. У...
Saved in:
| Date: | 2021 |
|---|---|
| Main Authors: | , , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
2021
|
| Subjects: | |
| Online Access: | https://jais.net.ua/index.php/files/article/view/178 |
| 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-178 |
|---|---|
| record_format |
ojs |
| institution |
Problems of Control and Informatics |
| baseUrl_str |
|
| datestamp_date |
2024-03-14T10:54:41Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
відмовостійкі мережі сценарій відмов методи декомпозиції r-алгоритми білінійна диференціальна реалізація із запізненням Gurobi |
| spellingShingle |
відмовостійкі мережі сценарій відмов методи декомпозиції r-алгоритми білінійна диференціальна реалізація із запізненням Gurobi Stetsyuk , Petro Lykhovyd , Oleksii Zhydkov , Volodymyr Suprun , Anton Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж |
| topic_facet |
отказоустойчивые сети сценарий отказов методы декомпозиции r-алгоритмы Gurobi відмовостійкі мережі сценарій відмов методи декомпозиції r-алгоритми білінійна диференціальна реалізація із запізненням Gurobi отказоустойчивые сети сценарий отказов методы декомпозиции r-алгоритмы Gurobi fault-tolerant networks failures scenario decomposition methods -algorithm r-algorithm |
| format |
Article |
| author |
Stetsyuk , Petro Lykhovyd , Oleksii Zhydkov , Volodymyr Suprun , Anton |
| author_facet |
Stetsyuk , Petro Lykhovyd , Oleksii Zhydkov , Volodymyr Suprun , Anton |
| author_sort |
Stetsyuk , Petro |
| title |
Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж |
| title_short |
Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж |
| title_full |
Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж |
| title_fullStr |
Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж |
| title_full_unstemmed |
Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж |
| title_sort |
оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж |
| title_alt |
Optimization problems of modernization of the capacity of arcs of fault-tolerant networks Оптимизационные задачи модернизации пропускных способностей дуг отказоустойчивых сетей |
| description |
Розглянуто математичні моделі двох класів задач модернізації пропускних здатностей дуг відмовостійких орієнтованих мереж. Відмовостійкою вважається мережа, для якої можна задовольнити всі вимоги на передачу потоків, якщо матиме місце одна, будь-яка відмова, з усіх можливих одиничних відмов мережі. У першому класі задач (задача A) для передачі потоків можуть використовуватись всі можливі шляхи в мережі. У другому класі задач (задача P) для передачі потоків задіяно тільки шляхи із напередзаданої множини шляхів. Математичні моделі представлено задачами лінійного, булевого та нелінійного програмування з блочною структурою матриці обмежень. Матеріал статті представлено в п’яти розділах. У розд. 1 описано поняття одиничної відмови та сценарію відмов мережі, наведено зміст оптимізаційних задач A та P для модернізації пропускних здатностей дуг відмовостійкої мережі, описано тестову мережу (6 вершин та 19 дуг) для перевірки алгоритмів розв’язання задач модернізації відмовостійких мереж. У розд. 2 описано базові моделі задач лінійного програмування для знаходження пропускних здатностей дуг відмовостійкої фізичної структури мережі (задача A) та відмовостійкої логічної структури мережі (задача P), розглянуто їх властивості. У розд. 3 описано задачі A та P у формі моделей змішаного булевого лінійного програмування. Наведено оптимальні розв’язки задачі A для різних сценаріїв відмов на прикладі тестової мережі. Розв’язки знайдено за допомогою програми Gurobi з NEOS-сервера, де математичну модель задачі A описано мовою моделювання AMPL. У розд. 4 описано нелінійні моделі опуклого програмування для задач A та P, призначені для знаходження оптимальних за вибраним критерієм пропускних здатностей дуг відмовостійких мереж, та описано декомпозиційний алгоритм їх розв’язання. У розд. 5 наведено опис програмного забезпечення мовою програмування ФОРТРАН для декомпозиційного алгоритму на основі ефективних реалізацій r-алгоритмів Шора. Проведено порівняння декомпозиційного алгоритму з програмою IPOPT на основі результатів розв’язання тестових задач. |
| publisher |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine |
| publishDate |
2021 |
| url |
https://jais.net.ua/index.php/files/article/view/178 |
| work_keys_str_mv |
AT stetsyukpetro optimízacíjnízadačímodernízacíípropusknihzdatnostejdugvídmovostíjkihmerež AT lykhovydoleksii optimízacíjnízadačímodernízacíípropusknihzdatnostejdugvídmovostíjkihmerež AT zhydkovvolodymyr optimízacíjnízadačímodernízacíípropusknihzdatnostejdugvídmovostíjkihmerež AT suprunanton optimízacíjnízadačímodernízacíípropusknihzdatnostejdugvídmovostíjkihmerež AT stetsyukpetro optimizationproblemsofmodernizationofthecapacityofarcsoffaulttolerantnetworks AT lykhovydoleksii optimizationproblemsofmodernizationofthecapacityofarcsoffaulttolerantnetworks AT zhydkovvolodymyr optimizationproblemsofmodernizationofthecapacityofarcsoffaulttolerantnetworks AT suprunanton optimizationproblemsofmodernizationofthecapacityofarcsoffaulttolerantnetworks AT stetsyukpetro optimizacionnyezadačimodernizaciipropusknyhsposobnostejdugotkazoustojčivyhsetej AT lykhovydoleksii optimizacionnyezadačimodernizaciipropusknyhsposobnostejdugotkazoustojčivyhsetej AT zhydkovvolodymyr optimizacionnyezadačimodernizaciipropusknyhsposobnostejdugotkazoustojčivyhsetej AT suprunanton optimizacionnyezadačimodernizaciipropusknyhsposobnostejdugotkazoustojčivyhsetej |
| first_indexed |
2025-10-30T02:48:45Z |
| last_indexed |
2025-10-30T02:48:45Z |
| _version_ |
1847373359033090048 |
| spelling |
oai:ojs2.jais.net.ua:article-1782024-03-14T10:54:41Z Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж Optimization problems of modernization of the capacity of arcs of fault-tolerant networks Оптимизационные задачи модернизации пропускных способностей дуг отказоустойчивых сетей Stetsyuk , Petro Lykhovyd , Oleksii Zhydkov , Volodymyr Suprun , Anton отказоустойчивые сети сценарий отказов методы декомпозиции r-алгоритмы Gurobi відмовостійкі мережі сценарій відмов методи декомпозиції r-алгоритми , білінійна диференціальна реалізація із запізненням Gurobi отказоустойчивые сети сценарий отказов методы декомпозиции r-алгоритмы Gurobi fault-tolerant networks failures scenario decomposition methods -algorithm r-algorithm Розглянуто математичні моделі двох класів задач модернізації пропускних здатностей дуг відмовостійких орієнтованих мереж. Відмовостійкою вважається мережа, для якої можна задовольнити всі вимоги на передачу потоків, якщо матиме місце одна, будь-яка відмова, з усіх можливих одиничних відмов мережі. У першому класі задач (задача A) для передачі потоків можуть використовуватись всі можливі шляхи в мережі. У другому класі задач (задача P) для передачі потоків задіяно тільки шляхи із напередзаданої множини шляхів. Математичні моделі представлено задачами лінійного, булевого та нелінійного програмування з блочною структурою матриці обмежень. Матеріал статті представлено в п’яти розділах. У розд. 1 описано поняття одиничної відмови та сценарію відмов мережі, наведено зміст оптимізаційних задач A та P для модернізації пропускних здатностей дуг відмовостійкої мережі, описано тестову мережу (6 вершин та 19 дуг) для перевірки алгоритмів розв’язання задач модернізації відмовостійких мереж. У розд. 2 описано базові моделі задач лінійного програмування для знаходження пропускних здатностей дуг відмовостійкої фізичної структури мережі (задача A) та відмовостійкої логічної структури мережі (задача P), розглянуто їх властивості. У розд. 3 описано задачі A та P у формі моделей змішаного булевого лінійного програмування. Наведено оптимальні розв’язки задачі A для різних сценаріїв відмов на прикладі тестової мережі. Розв’язки знайдено за допомогою програми Gurobi з NEOS-сервера, де математичну модель задачі A описано мовою моделювання AMPL. У розд. 4 описано нелінійні моделі опуклого програмування для задач A та P, призначені для знаходження оптимальних за вибраним критерієм пропускних здатностей дуг відмовостійких мереж, та описано декомпозиційний алгоритм їх розв’язання. У розд. 5 наведено опис програмного забезпечення мовою програмування ФОРТРАН для декомпозиційного алгоритму на основі ефективних реалізацій r-алгоритмів Шора. Проведено порівняння декомпозиційного алгоритму з програмою IPOPT на основі результатів розв’язання тестових задач. Mathematical models of two classes of problems of modernization of the capacity of arcs of fault-tolerant oriented networks are considered. A network is considered to be fault-tolerant for which it is possible to satisfy all the demands for the transmission of flows when there will be one, but any failure, from all possible single network failures. For the first class of problems (problem A), all possible paths in the network can be used for the transmission of flows. For the second class of problems (problem P), only paths from a predetermined set of paths are used to transfer flows. Mathematical models are represented by linear, Boolean and nonlinear programming problems with a block structure of the constraint matrix.The material of the article is presented in five sections. The first section describes the concepts of a single failure and the scenario of network failures, the content of optimization problems A and P for modernization of capacity of arcs of a fault-tolerant network, a test network (6 vertices and 19 arcs) to test algorithms for solving the problems of modernization of fault-tolerant networks. In the second section, basic models of linear programming problems for finding the capacities of arcs of the fault-tolerant physical structure of a network (problem A) and the fault-tolerant logical structure of a network (problem P) are described, and their properties are considered. The third section describes problems A and P in the form of mixed Boolean linear programming models. Optimal solutions of problem A for various failure scenarios are given for the example of the test network. The solutions were found using the Gurobi program from the NEOS server, where the mathematical model of problem A is described in the AMPL modeling language.The fourth section describes nonlinear convex programming models for problems A and P, developed to find the optimal capacities of fault-tolerant networks according to the selected criterion, and a decomposition algorithm for their solution. The fifth section describes software in the FORTRAN programming language for the decomposition algorithm based on efficient implementations of Shor’s r-algorithms. The decomposition algorithm is compared with the IPOPT program based on the results of solving test problems. Рассмотрены математические модели двух классов задач модернизации пропускных способностей дуг отказоустойчивых ориентированных сетей. Отказостойкой считается сеть, для которой можно удовлетворить все требования на передачу потоков, если будет иметь место один, любой отказ, из всех возможных единичных отказов сети. В первом классе задач (задача A) для передачи потоков могут использоваться все возможные пути в сети. Во втором классе задач (задача P) для передачи потоков задействованы только пути из предзаданного множества путей. Математические модели представлены задачами линейного, булевого и нелинейного программирования с блочной структурой матрицы ограничений. Материал статьи представлен в пяти главах. В разд. 1 описано понятие единичного отказа и сценария отказов сети, приведено содержание оптимизационных задач A и P для модернизации пропускных способностей дуг отказоустойчивой сети, описана тестовая сеть (6 вершин и 19 дуг) для проверки алгоритмов решения задач модернизации отказа. сетей. В разд. 2 описаны базовые модели задач линейного программирования для нахождения пропускных способностей дуг отказоустойчивой физической структуры сети (задача A) и отказоустойчивой логической структуры сети (задача P), рассмотрены их свойства. В разд. 3 описаны задачи A и P в форме моделей смешанного булевого линейного программирования. Приведены оптимальные решения задачи A для различных сценариев отказов на примере тестовой сети. Решения найдены с помощью программы Gurobi из NEOS-сервера, где математическая модель задачи A описана на языке моделирования AMPL. В разд. 4 описаны нелинейные модели выпуклого программирования для задач A и P, предназначенные для нахождения оптимальных по выбранному критерию пропускных способностей дуг отказоустойчивых сетей, и описан декомпозиционный алгоритм их решения. В разд. 5 приведено описание программного обеспечения языком программирования ФОРТРАН для декомпозиционного алгоритма на основе эффективных реализаций r-алгоритмов Шора. Проведено сравнение декомпозиционного алгоритма с программой IPOPT на основе результатов решения тестовых задач. V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2021-08-25 Article Article application/pdf https://jais.net.ua/index.php/files/article/view/178 10.34229/1028-0979-2021-5-1 Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; Том 66 № 5 (2021): Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; 5-20 International Scientific Technical Journal "Problems of Control and Informatics; Том 66 № 5 (2021): International Scientific and Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 5-20 International Scientific Technical Journal "Problems of Control and Informatics"; Vol. 66 No. 5 (2021): International Scientific and Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 5-20 2786-6505 2786-6491 10.34229/1028-0979-2021-5 uk https://jais.net.ua/index.php/files/article/view/178/267 Copyright (c) 2021 Petro Stetsyuk , Oleksii Lykhovyd , Volodymyr Zhydkov , Anton Suprun https://creativecommons.org/licenses/by-nc-nd/4.0 |