Оптимізаційні задачі модернізації пропускних здатностей дуг відмовостійких мереж

Abstract

Розглянуто математичні моделі двох класів задач модернізації пропускних здатностей дуг відмовостійких орієнтованих мереж. Відмовостійкою вважається мережа, для якої можна задовольнити всі вимоги на передачу потоків, якщо матиме місце одна, будь-яка відмова, з усіх можливих одиничних відмов мережі. У першому класі задач (задача 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.