Citeseer/Stabilized Column Generation for the Temporal Knapsack Problem using Dual-Optimal Inequalities 10.1.1.736.7664 — различия между версиями
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) м (StasFomin переименовал страницу Citeseer/Stabilized Column Generation for the Temporal Knapsack Problem usingDual-Optimal Inequalities 10.1.1.736.7664 в [[Citeseer/Stabilized Column Generation for the Temporal Knapsack Problem…) |
(нет различий)
|
Текущая версия на 15:54, 23 ноября 2021
«Stabilized Column Generation for the Temporal Knapsack Problem usingDual-Optimal Inequalities 10.1.1.736.7664»скачать
Мы представляем два новых метода стабилизации алгоритмов генерации столбцов для временной задачи о ранце (Temporal Knapsack Problem, TKP). Впервые мы предложили использовать алгоритмы ветвления и цены для переформулировок Данцига-Вольфа для TKP.
В данном случае соответствующие задачи ценообразования представляют собой TKP меньшего размера, которые могут быть решены с помощью ЦЛП/MIP-решателя общего назначения или динамического программирования.
Наши методы стабилизации адаптированы к ТКП, поскольку они используют (глубокие) двойственные оптимальные неравенства, то есть неравенства, которые, как известно, выполняются всеми (по крайней мере, некоторыми) оптимальными двойственными решениями линейной релаксации.
…»