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-решателя общего назначения или динамического программирования.
Наши методы стабилизации адаптированы к ТКП, поскольку они используют (глубокие) двойственные оптимальные неравенства, то есть неравенства, которые, как известно, выполняются всеми (по крайней мере, некоторыми) оптимальными двойственными решениями линейной релаксации.
…»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.