The Dynamic and Stochastic Knapsack Problem.pdfVIP

The Dynamic and Sto chastic Knapsack Problem y Anton J. Kleywegt Scho ol of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332-020 5 Jason D. Papastavrou Scho ol of Industrial Engineering Purdue University West Lafayette, IN 47907-1287 Abstract The Dynamic and Sto chastic Knapsack Problem (DSKP) is de ned as follows: Items arrive according to a Poisson pro cess in time. Each item has a demand (size) for a limited resource (the knapsack) and an asso ciated reward. The resource requirements and rewards are jointly distributed according to a known probabili ty distributio n and b ecome known at the time of the items arrival. Items can b e either accepted or rejected. If an item is accepted, the items reward is received, and if an item is rejected, a p enalty is paid. The problem can b e stopp ed at any time, at which time a terminal value is received, which may dep end on the amount of resource remaining. Given the waiting cost and the time horizon of the problem, the ob jective is to determine the optimal p olicy that maximizes the exp ected value (rewards minus costs) accumulated. Assuming that all items have equal sizes but random rewards, optimal solutions are derived for a variety of cost structures and time horizons, and recursive algorithms for computing them are develop ed. Optimal closed-form solutions are obtained for sp ecial cases. The DSKP has applicati ons in freig