Снижение размерности задачи нахождения критических узлов сети

Автор(ы): Крыгин А.А., Тарасова С.М.

Выпуск: 111

Рубрика: Сетевые модели в управлении

Год: 2024

Библиография: Крыгин А.А., Тарасова С.М. Снижение размерности задачи нахождения критических узлов сети // Управление большими системами. Выпуск 111. М.: ИПУ РАН, 2024. С.118-146. DOI: https://doi.org/10.25728/ubs.2024.111.5

Дата опубликования: 30.09.2024

Ключевые слова: устойчивость электрических сетей, поиск критических узлов, графовые модели сетей

Аннотация: Одним из классов задач, решаемых при оценке устойчивости инженерной сети, являются задачи нахождения критических узлов. В ряде постановок эта задача формулируется как нахождение такого подмножества узлов заданной мощности (критических узлов), при выходе из строя которых всей сети будет нанесен максимальный ущерб. И наиболее частый способ оценки ущерба в такой постановке -- определение количества связных пар узлов в сети с исключенными критическими узлами. Для таких узлов, которые соответствуют минимуму количества связных пар, требуются проведение дополнительных мер по повышению надежности и безопасности. Ряд методов решения задачи нахождения критических узлов использует сведение ее к эквивалентной задаче линейного программирования. Основной проблемой этого подхода является большая размерность задачи, и, как следствие, высокая вычислительная сложность ее решения. В работе проводится исследование различных характеристик вершин графовой модели сети, анализ значений которых позволит заранее установить факт принадлежности вершины к подмножеству критических или наоборот, к подмножеству некритических узлов. Благодаря этому можно сформировать дополнительные ограничения, снижающие размерность задачи линейного программирования и ее вычислительную сложность, что позволит находить критические узлы в инженерных сетях с большим количеством объектов за приемлемое время. В процессе исследования было решено множество различных подзадач, поэтому в работе описывается первая, подготовительная его часть.

Author(s): Krygin A., Tarasova S.

Article title: Reduction the dimensionality of the task of finding critical nodes in the network

Issue: 111

Year: 2024

Keywords: resilience of electrical networks, search for critical nodes, graph models of networks

Abstract: One of the classes of problems solved in the assessment of the stability of an engineering network is the problem of finding critical nodes. In many formulations, this problem is posed as finding a subset of nodes of a given cardinality (critical nodes) such that the failure of which would cause maximum damage to the entire network. And the most common way to assess the damage in such a formulation is to determine the number of connected node pairs in the network with excluded critical nodes. For such nodes that correspond to the minimum number of connected pairs, additional measures are required to increase reliability and safety. Several methods of solving the problem of finding critical nodes use reducing it to an equivalent linear programming problem. The main problem of this approach is the large size of the problem, and consequently, the high computational complexity of its solution. The work conducts research on various characteristics of vertices of a graph model of a network, the analysis of the values of which will allow determining in advance the fact of belonging to the subset of critical or, conversely, to the subset of non-critical nodes. Thanks to this, it is possible to form additional constraints that reduce the dimensionality of the linear programming problem and its computational complexity, which will allow finding critical nodes in engineering networks with a large number of objects in an acceptable time. During the research, a large number of different subproblems were solved, so the work describes only the first, preparatory part of it.