Article ID: | iaor200954197 |
Country: | United States |
Volume: | 33 |
Issue: | 4 |
Start Page Number: | 945 |
End Page Number: | 964 |
Publication Date: | Nov 2008 |
Journal: | Mathematics of Operations Research |
Authors: | Goemans Michel X, Dean Brian C, Vondrk Jan |
Keywords: | programming: integer |
We consider a stochastic variant of the NP–hard 0/1 knapsack problem, in which item values are deterministic and item sizes are independent random variables with known, arbitrary distributions. Items are placed in the knapsack sequentially, and the act of placing an item in the knapsack instantiates its size. Our goal is to compute a solution “policy” that maximizes the expected value of items successfully placed in the knapsack, where the final overflowing item contributes no value. We consider both