TECHNICAL NOTE - The Adaptive Knapsack Problem with Stochastic Rewards
TECHNICAL NOTE - The Adaptive Knapsack Problem with Stochastic Rewards
复制标题
技术说明 - 具有随机奖励的自适应背包问题
DOI：
10.1287/opre.1100.0857
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Mark S. Daskin
中科院分区：
文献类型：
--
作者：
Taylan Ilhan;S. Iravani;Mark S. Daskin
给定一组具有确定性权重和随机奖励的物品，自适应随机背包问题（自适应SKP）在每个物品的奖励实现之前，当物品顺序插入到容量限制的背包中时，最大化达到预定目标奖励水平的概率。这个模型出现在资源分配问题，允许或需要顺序分配决策的概率设置。一个特别的应用是在陈旧库存管理。本文将自适应SKP表示为离散随机奖励的动态规划（DP）问题。本文还提出了一种启发式的混合自适应和静态的政策，以克服“灾难的维度”的DP。建议的启发式扩展到正态分布的随机奖励的问题。启发式可以快速解决大型问题，其解决方案总是优于静态策略。数值研究表明，一个接近最优的解决方案，可以通过使用有限的前瞻能力的算法。
Given a set of items with associated deterministic weights and random rewards, the adaptive stochastic knapsack problem (adaptive SKP) maximizes the probability of reaching a predetermined target reward level when items are inserted sequentially into a capacitated knapsack before the reward of each item is realized. This model arises in resource allocation problems that permit or require sequential allocation decisions in a probabilistic setting. One particular application is in obsolescence inventory management. In this paper, the adaptive SKP is formulated as a dynamic programming (DP) problem for discrete random rewards. The paper also presents a heuristic that mixes adaptive and static policies to overcome the “curse of dimensionality” in the DP. The proposed heuristic is extended to problems with normally distributed random rewards. The heuristic can solve large problems quickly, and its solution always outperforms a static policy. The numerical study indicates that a near-optimal solution can be obtained by using an algorithm with limited look-ahead capabilities.