Citeseer/Convexity and solutions of stochastic Multidimensional Knapsack Problems with Probabilistic Constraints (2012) 10.1.1.258.3304 — различия между версиями
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
{{checked|}} | {{checked|}} | ||
− | {{citeseerlink|citeseer/Convexity and solutions of stochastic Multidimensional Knapsack Problems with Probabilistic Constraints (2012) 10.1.1.258.3304| | + | {{citeseerlink|citeseer/Convexity and solutions of stochastic Multidimensional Knapsack Problems with Probabilistic Constraints (2012) 10.1.1.258.3304| |
+ | В многомерной задаче о ранце задан набор предметов, каждый из которых имеет стоимость и многомерный размер, и мы хотим выбрать подмножество из них таким образом, чтобы общая стоимость выбранных предметов была максимальной, а общий размер удовлетворял некоторому ограничению емкости для каждого измерения. | ||
+ | В данной работе мы предполагаем, что размеры являются независимыми случайными величинами, причем каждый размер имеет один и тот же тип распределения вероятности, не обязательно с одним и тем же параметром. | ||
− | + | На ограничения емкости накладывается совместное вероятностное ограничение, а целевая функция такая же, как и в основной детерминированной задаче. | |
+ | |||
+ | Мы показали, что задача является выпуклой, при некотором условии на параметры, для специальных непрерывных и дискретных распределений: гамма, нормального, Пуассона и биномиального, где две последние функции дискретного распределения аппроксимируются логново-вогнутыми функциями непрерывного распределения. | ||
+ | }} | ||
[[Участник:StasFomin|StasFomin]] 09:42, 23 ноября 2021 (UTC):своего алгоритма у них нет, много зубодробительного анализа в среднем, и потом они гоняют промышленные солверы... все равно можно попробовать. | [[Участник:StasFomin|StasFomin]] 09:42, 23 ноября 2021 (UTC):своего алгоритма у них нет, много зубодробительного анализа в среднем, и потом они гоняют промышленные солверы... все равно можно попробовать. |
Текущая версия на 15:15, 23 ноября 2021
«Convexity and solutions of stochastic Multidimensional Knapsack Problems with Probabilistic Constraints (2012) 10.1.1.258.3304»скачать
В многомерной задаче о ранце задан набор предметов, каждый из которых имеет стоимость и многомерный размер, и мы хотим выбрать подмножество из них таким образом, чтобы общая стоимость выбранных предметов была максимальной, а общий размер удовлетворял некоторому ограничению емкости для каждого измерения.
В данной работе мы предполагаем, что размеры являются независимыми случайными величинами, причем каждый размер имеет один и тот же тип распределения вероятности, не обязательно с одним и тем же параметром.
На ограничения емкости накладывается совместное вероятностное ограничение, а целевая функция такая же, как и в основной детерминированной задаче.
Мы показали, что задача является выпуклой, при некотором условии на параметры, для специальных непрерывных и дискретных распределений: гамма, нормального, Пуассона и биномиального, где две последние функции дискретного распределения аппроксимируются логново-вогнутыми функциями непрерывного распределения.
…»