Анализ устойчивости некоторых алгоритмов дискретной оптимизации

Приводится обзор результатов, полученных по устойчивости алгоритмов целочисленного программирования, которые основаны на использовании релаксационных множеств. Исследуется устойчивость алгоритмов ветвей и границ (в рамках метода Лэнд и Дойг) для задачи целочисленного линейного программирования. Показано, что эти алгоритмы не являются устойчивыми при достаточно малых колебаниях релаксационных множеств рассматриваемых задач. Аналогичный результат получен для алгоритмов с отсечениями Данцига.

Статья представлена к публикации членом редколлегии: А. И. Кибзун