Citeseer/Stabilized Column Generation for the Temporal Knapsack Problem using Dual-Optimal Inequalities 10.1.1.736.7664 — различия между версиями

«Stabilized Column Generation for the Temporal Knapsack Problem usingDual-Optimal Inequalities 10.1.1.736.7664»^{скачать}

Мы представляем два новых метода стабилизации алгоритмов генерации столбцов для временной задачи о ранце (Temporal Knapsack Problem, TKP). Впервые мы предложили использовать алгоритмы ветвления и цены для переформулировок Данцига-Вольфа для TKP.

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

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