Подробное описание документа

Заславский А. А., Лебедев С. С.
   Метод узловых векторов целочисленного программирования / Заславский А. А., Лебедев С. С. ; Российская академия наук, Центральный экономико-математический институт. - М. : Изд-во центрального экономико-математического ин-та, 2000. - 82 с. - Библиогр.: с. 80-81. - Препринт #WP/2000/094. - ISBN 5-8211-0102-6.

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