Общая задача синтеза надежных сетей

Abstract

Розглядається важлива для розвитку теорії та практики задача проектування мережі мінімальної вартості, що продовжує функціонувати навіть при виході з ладу окремих її компонент. Кількість обмежень в моделі з потоковими змінними 0 та 1 експоненційно залежить від кількості вузлів; показано, що LP -релаксація цієї задачі NP -складна. Для окремих випадків доведено, що розв’язок відповідної LP -релаксації цієї задачі можна знайти за допомогою поліноміального алгоритму. Запропоновано ефективні алгоритми обчислення верхньої та нижньої границь для двозв’язної задачі Штейнера. Для розв’язання цієї задачі застосовується метод гілок та границь; наведено також результати обчислювальних експериментів.

We consider the important practical and theoretical problem of designing communications network with a minimum total cost under condition that an optimal network must survive with respect to failures of certain its components. The model with 0, 1 — flow variables contains a number of constraints that is exponential in the number of nodes and we show that its LP -relaxation is NP -complete problem. For some particular cases, we prove that a solution of LP -relaxation problem can be found by polynomial time algorithm. We propose effective algorithms to compute lower and upper bounds for the two connected Steiner problem. For finding a solution of this problem we implement the branch and bound algorithm and we also report on some computational results.