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.

Кроме того, мы исследуем многочисленные стратегии генерации столбцов и методы создания дополнительных столбцов вне задачи ценообразования. проблемы.