The adaptive knapsack problem with stochastic rewards

Taylan Lihan*, Seyed MR Iravani, Mark S. Daskin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)242-248
Number of pages7
JournalOperations Research
Volume59
Issue number1
DOIs
StatePublished - Jan 1 2011

Keywords

  • Dynamic programming
  • Sequential decision analysis

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'The adaptive knapsack problem with stochastic rewards'. Together they form a unique fingerprint.

Cite this