М. В. Девятерикова, А. А. Колоколов, Н. А. Косарев, “Анализ устойчивости по целевой функции некоторых алгоритмов целочисленного программирования”, Изв. вузов. Матем., 2011, номер 4,страницы 23

Эта публикация цитируется в 3 статьях

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

М. В. Девятерикова^a, А. А. Колоколов^bc, Н. А. Косарев^c

^a Кафедра прикладной математики и информационных систем, Омский государственный технический университет, г. Омск
^b Кафедра прикладной и вычислительной математики, Омский государственный университет, г. Омск
^c Омский филиал Института математики им. С. Л. Соболева СО РАН, г. Омск

Аннотация: Вводится определение устойчивости по целевой функции для достаточно широкого класса алгоритмов целочисленного программирования. Изучается устойчивость некоторых из них при малых колебаниях коэффициентов целевых функций решаемых задач. Показано, что существуют как устойчивые, так и неустойчивые варианты алгоритмов перебора $L$-классов. Установлена неустойчивость ряда алгоритмов ветвей и границ и декомпозиционных алгоритмов с отсечениями Бендерса. Предложена модификация рассматриваемых декомпозиционных алгоритмов, позволяющая обеспечить свойство устойчивости.

Ключевые слова: дискретная оптимизация, целочисленное программирование, устойчивость алгоритмов, перебор $L$-классов, метод ветвей и границ, декомпозиция Бендерса.

УДК: 519.854

Поступила: 20.10.2009