Citeseer/Column generation strategies and decomposition approaches to the size robust multiple knapsack problem (2015) 10.1.1.730.8463 — различия между версиями
StasFomin (обсуждение | вклад) (Новая страница: «{{checked|}} {{citeseerlink|citeseer/Column generation strategies and decomposition approaches to the size robust multiple knapsack problem (2015) 10.1.1.730.8463…») |
StasFomin (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
{{checked|}} | {{checked|}} | ||
− | {{citeseerlink|citeseer/Column generation strategies and decomposition approaches to the size robust multiple knapsack problem (2015) 10.1.1.730.8463| | + | {{citeseerlink|citeseer/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. | ||
+ | |||
+ | Кроме того, мы исследуем многочисленные стратегии генерации столбцов и методы создания дополнительных столбцов вне задачи ценообразования. | ||
+ | проблемы. | ||
+ | }} | ||
{{enddiv}} | {{enddiv}} | ||
[[Категория:CiteSeerArticles]] | [[Категория:CiteSeerArticles]] |
Текущая версия на 15:07, 23 ноября 2021
«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.
Кроме того, мы исследуем многочисленные стратегии генерации столбцов и методы создания дополнительных столбцов вне задачи ценообразования. проблемы.
…»