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

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