Программа NETWORK_COVER предназначена для оптимизации выбора множества колец, используемых для защиты сетей. Например, выбора расположения BLSR колец для защитного покрытия оптоволоконной сети.

Задача оптимизации выбора защитных колец может быть сформулирована в виде задачи покрытия целочисленного линейного программирования, где переменные представляют все возможные кольца в защищаемой сети. Стандартный подход заключается в решении данной целочисленной линейной программы (ЦЛП). Недостаток данного метода заключается в экспонециальном росте числа переменных при линейном росте размера сети, и как следствие невозможность решения (вследствие NP-полноты) данной ЦЛП.

Основная идея наших алгоритмов заключается в достаточно быстром выделении относительного небольшого множества "перспективных" колец, с последующим решением ограниченной этими кольцами ЦЛП. Для выделения таких колец используются вероятностные алгоритмы решения двойственной задачи линейной релаксации исходной задачи ЦЛП.