TECHNICAL NOTE---The Adaptive Knapsack Problem with Stochastic Rewards

Taylan İlhan (), Seyed M. R. Iravani () and Mark S. Daskin ()
Additional contact information
Taylan İlhan: Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois 60208
Seyed M. R. Iravani: Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois 60208
Mark S. Daskin: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109

Operations Research, 2011, vol. 59, issue 1, 242-248

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.

Keywords: dynamic programming; sequential decision analysis (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1100.0857 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:59:y:2011:i:1:p:242-248

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().