Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж
Розглянуто математичні моделі двох класів задач модернізації пропускних здатностей дуг відмовостійких орієнтованих мереж. Відмовостійкою вважається мережа, для якої можна задовольнити всі вимоги на передачу потоків, якщо матиме місце одна, будь-яка відмова, з усіх можливих одиничних відмов мережі. У...
Gespeichert in:
| Veröffentlicht in: | Проблемы управления и информатики |
|---|---|
| Datum: | 2021 |
| Hauptverfasser: | , , , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2021
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/209001 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж / П.І. Стецюк, О.П. Лиховид , В.О. Жидков, А.А. Супрун // Проблемы управления и информатики. — 2021. — № 5. — С. 5–20. — Бібліогр.: 31 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-209001 |
|---|---|
| record_format |
dspace |
| spelling |
Стецюк, П.І. Лиховид, О.П. Жидков, В.О. Супрун, А.А. 2025-11-10T17:17:09Z 2021 Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж / П.І. Стецюк, О.П. Лиховид , В.О. Жидков, А.А. Супрун // Проблемы управления и информатики. — 2021. — № 5. — С. 5–20. — Бібліогр.: 31 назв. — укр. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/209001 519.85 10.34229/1028-0979-2021-5-1 Розглянуто математичні моделі двох класів задач модернізації пропускних здатностей дуг відмовостійких орієнтованих мереж. Відмовостійкою вважається мережа, для якої можна задовольнити всі вимоги на передачу потоків, якщо матиме місце одна, будь-яка відмова, з усіх можливих одиничних відмов мережі. У першому класі задач (задача 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. Робота підтримана CRDF Global (грант G-202102-68020). uk Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы оптимизации и оптимальное управление Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж Оптимизационные задачи модернизации пропускных способностей дуг отказоустойчивых сетей Optimization problems for modernizing the throughput capacities of arcs in fault-tolerant networks Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж |
| spellingShingle |
Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж Стецюк, П.І. Лиховид, О.П. Жидков, В.О. Супрун, А.А. Методы оптимизации и оптимальное управление |
| title_short |
Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж |
| title_full |
Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж |
| title_fullStr |
Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж |
| title_full_unstemmed |
Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж |
| title_sort |
оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж |
| author |
Стецюк, П.І. Лиховид, О.П. Жидков, В.О. Супрун, А.А. |
| author_facet |
Стецюк, П.І. Лиховид, О.П. Жидков, В.О. Супрун, А.А. |
| topic |
Методы оптимизации и оптимальное управление |
| topic_facet |
Методы оптимизации и оптимальное управление |
| publishDate |
2021 |
| language |
Ukrainian |
| container_title |
Проблемы управления и информатики |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Оптимизационные задачи модернизации пропускных способностей дуг отказоустойчивых сетей Optimization problems for modernizing the throughput capacities of arcs in fault-tolerant networks |
| issn |
0572-2691 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/209001 |
| citation_txt |
Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж / П.І. Стецюк, О.П. Лиховид , В.О. Жидков, А.А. Супрун // Проблемы управления и информатики. — 2021. — № 5. — С. 5–20. — Бібліогр.: 31 назв. — укр. |
| work_keys_str_mv |
AT stecûkpí optimízacíinízadačímodernízacíípropusknihzdatnosteidugvídmovostíikihmerež AT lihovidop optimízacíinízadačímodernízacíípropusknihzdatnosteidugvídmovostíikihmerež AT židkovvo optimízacíinízadačímodernízacíípropusknihzdatnosteidugvídmovostíikihmerež AT suprunaa optimízacíinízadačímodernízacíípropusknihzdatnosteidugvídmovostíikihmerež AT stecûkpí optimizacionnyezadačimodernizaciipropusknyhsposobnosteidugotkazoustoičivyhsetei AT lihovidop optimizacionnyezadačimodernizaciipropusknyhsposobnosteidugotkazoustoičivyhsetei AT židkovvo optimizacionnyezadačimodernizaciipropusknyhsposobnosteidugotkazoustoičivyhsetei AT suprunaa optimizacionnyezadačimodernizaciipropusknyhsposobnosteidugotkazoustoičivyhsetei AT stecûkpí optimizationproblemsformodernizingthethroughputcapacitiesofarcsinfaulttolerantnetworks AT lihovidop optimizationproblemsformodernizingthethroughputcapacitiesofarcsinfaulttolerantnetworks AT židkovvo optimizationproblemsformodernizingthethroughputcapacitiesofarcsinfaulttolerantnetworks AT suprunaa optimizationproblemsformodernizingthethroughputcapacitiesofarcsinfaulttolerantnetworks |
| first_indexed |
2025-12-07T17:37:21Z |
| last_indexed |
2025-12-07T17:37:21Z |
| _version_ |
1850886039335337984 |
| 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 на основі результатів розв’язання тестових задач.
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.
|