Citeseer/Column generation strategies and decomposition approaches to the size robust multiple knapsack problem (2015) 10.1.1.730.8463
«Column generation strategies and decomposition approaches to the size robust multiple knapsack problem (2015) 10.1.1.730.8463»скачать
Многие проблемы могут быть сформулированы в виде вариантов проблем ранца. Однако такие модели являются детерминированными, в то время как многие реальные проблемы включают в себя некоторую неопределенность. Поэтому стоит разработать и протестировать модели ранцев, которые могут иметь дело с возмущениями.
В данной работе мы рассматриваем устойчивую по размеру проблему множественного ранца — задачу с несколькими ранцами и набором возможных возмущений.
- Для каждого возмущения, или сценария, мы знаем вероятность его возникновения и результирующее уменьшение размеров рюкзаков.
- Для борьбы с этими возмущениями мы используем восстанавливаемую устойчивость.
Восстанавливаемая устойчивость требует, чтобы мы нашли решение, которое выполнимо для случая без нарушений, в то время как в случае с нарушениями, мы можем скорректировать решение с помощью простого алгоритма восстановления, который в нашем случае заключается в удалении элементов из соответствующего ранца.
Наша цель — найти решение, при котором ожидаемый доход будет максимальным. Для решения этой задачи мы используем метод ветвей и цен.
Мы представляем и сравниваем два подхода к решению:
- раздельное разложение восстановления (SRD)
- и комбинированное разложение восстановления (CRD).
Мы доказываем, что LP-релаксация модели CRD сильнее, чем LP-релаксация модели SRD.
Кроме того, мы исследуем многочисленные стратегии генерации столбцов и методы создания дополнительных столбцов вне задачи ценообразования. проблемы.
…»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.