Просмотр исходного текста страницы Citeseer/Stabilized Column Generation for the Temporal Knapsack Problem using Dual-Optimal Inequalities 10.1.1.736.7664

{{checked|}}
{{citeseerlink|citeseer/Stabilized Column Generation for the Temporal Knapsack Problem usingDual-Optimal Inequalities 10.1.1.736.7664|
Мы представляем два новых метода стабилизации алгоритмов генерации столбцов для временной задачи о ранце (Temporal Knapsack Problem, TKP).
Впервые мы предложили использовать алгоритмы ветвления и цены для переформулировок Данцига-Вольфа для TKP. 

В данном случае соответствующие задачи ценообразования представляют собой TKP меньшего размера, которые могут быть решены с помощью ЦЛП/MIP-решателя общего назначения или динамического программирования. 

Наши методы стабилизации адаптированы к ТКП, поскольку они используют (глубокие) двойственные оптимальные неравенства, то есть неравенства, которые, как известно, выполняются всеми (по крайней мере, некоторыми) оптимальными двойственными решениями линейной релаксации.
}}
{{enddiv}}

[[Категория:CiteSeerArticles]]