Аннотация
Заславский А.А., Лебедев С.С.Метод узловых векторов целочисленного программирования. I. Общая задача частично целочисленного линейного программирования с неотрицательными коэффициентами. / Препринт # WP/2000/094. - М.: ЦЭМИ РАН, 2000. - 81 с. (Рус.)
Описан новый метод частично целочисленного линейного программирования. С помощью процедуры упорядочивающей индексации генерируются варианты - фиксированные векторы целочисленных переменных. Задача линейного программирования (ЛП), соответствующая некоторому варианту, определяет так называемый узловой вектор множителей Лагранжа. Узловые векторы используются при построении оценок для других вариантов. В результате метод отсеивает большинство генерируемых вариантов без решения соответствующих им задач ЛП.
Приведен новый алгоритм упорядочивающей индексации для обобщенной задачи о рюкзаке. Описано несколько новых алгоритмов модифицированного метода пометок, которые можно использовать для генерации вариантов по сильным оценочным функциям комплексной структуры.
Работа выполнена при поддержке Российского фонда фундаментальных исследований. Код проекта 99-01-01125.
Приведен новый алгоритм упорядочивающей индексации для обобщенной задачи о рюкзаке. Описано несколько новых алгоритмов модифицированного метода пометок, которые можно использовать для генерации вариантов по сильным оценочным функциям комплексной структуры.
Работа выполнена при поддержке Российского фонда фундаментальных исследований. Код проекта 99-01-01125.
