Hostname: page-component-8448b6f56d-mp689 Total loading time: 0 Render date: 2024-04-19T20:35:45.667Z Has data issue: false hasContentIssue false
  • English
  • Français

STATIC STOCHASTIC KNAPSACK PROBLEMS

Published online by Cambridge University Press:  16 October 2015

Kai Chen  and
Sheldon M. Ross
Kai Chen
Affiliation:
Epstein Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, CA 90089, USA E-mails: kaic@usc.edu; smross@usc.edu
Sheldon M. Ross
Affiliation:
Epstein Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, CA 90089, USA E-mails: kaic@usc.edu; smross@usc.edu
Get access Rights & Permissions [Opens in a new window]

Abstract

Two stochastic knapsack problem (SKP) models are considered: the static broken knapsack problem (BKP) and the SKP with simple recourse and penalty cost problem. For both models, we assume: the knapsack has a constant capacity; there are n types of items and each type has an infinite supply; a type i item has a deterministic reward vi and a random weight with known distribution Fi. Both models have the same objective to maximize expected total return by finding the optimal combination of items, that is, quantities of items of each type to be put in knapsack. The difference between the two models is: if knapsack is broken when total weights of items put in knapsack exceed the knapsack's capacity, for the static BKP model, all existing rewards would be wiped out, while for the latter model, we could still keep the existing rewards in knapsack but have to pay a fixed penalty plus a variant cost proportional to the overcapacity amount. This paper also discusses the special case when knapsack has an exponentially distributed capacity.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 29 , Issue 4 , October 2015 , pp. 527 - 546
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. Ağralı, S. & Geunes, J. (2009). A single-resource allocation problem with Poisson resource requirements. Optimization Letters 3(4): 559–571.Google Scholar
2. An, M. (1997). Log-concave probability distributions: theory and statistical testing. Duke University Department of Economics Working Paper, (95-03).Google Scholar
3. Bergstrom, T. & Bagnoli, M. (2005). Log-concave probability and its applications. Economic Theory 26: 445–469.Google Scholar
4. Cohn, A.M. & Mit, C.B. (1998). The stochastic knapsack problem with random weights: a heuristic approach to robust transportation planning. In Proceedings of the Triennial Symposium on Transportation Analysis. Citeseer.Google Scholar
5. Dean, B.C., Goemans, M.X., & Vondrdk, J. (2004). Approximating the stochastic knapsack problem: the benefit of adaptivity. In 2004 Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, IEEE, pp. 208–217.Google Scholar
6. Derman, C., Lieberman, G.J., & Ross, S.M. (1978). A renewal decision problem. Management Science 24(5): 554–561.Google Scholar
7. Fortz, B., Labbé, M., Louveaux, F., & Poss, M. (2013). Stochastic binary problems with simple penalties for capacity constraints violations. Mathematical Programming 138 (1–2): 199–221.Google Scholar
8. Goel, A. & Indyk, P. (1999). Stochastic load balancing and related problems. In 1999, 40th Annual Symposium on Foundations of Computer Science, IEEE, pp. 579–586.Google Scholar
9. Henig, M.I. (1990). Risk criteria in a stochastic knapsack problem. Operations Research 38(5): 820–825.Google Scholar
10. S.M.R. Iravani Ilhan, T. & Daskin, M.S. (2011). The adaptive knapsack problem with stochastic rewards. Operations Research 59(1): 242–248.Google Scholar
11. Karlin, S. (1968). Total positivity. vol. 1. Stanford University Press.Google Scholar
12. Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack problems. Berlin, Heidelberg: Springer.Google Scholar
13. Kleinberg, J., Rabani, Y., & Tardos, É. (1997). Allocating bandwidth for bursty connections. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, ACM, pp. 664–673.Google Scholar
14. Kleywegt, A.J. & Papastavrou, J.D. (1998). The dynamic and stochastic knapsack problem. Operations Research 46: 17–35.Google Scholar
15. Kleywegt, A.J. & Papastavrou, J.D. (2001). The dynamic and stochastic knapsack problem with random sized items. Operations Research 49(1): 26–41.Google Scholar
16. Kolesar, P.J. (1967). A branch and bound algorithm for the knapsack problem. Management Science 13(9): 723–735.Google Scholar
17. Kosuch, S. & Lisser, A. (2010). Upper bounds for the 0–1 stochastic knapsack problem and a branch-and-bound algorithm. Annals of Operations Research 176: 77–93.Google Scholar
18. Kosuch, S. & Lisser, A. (2011). On two-stage stochastic knapsack problems. Discrete Applied Mathematics 159(16): 1827–1841.Google Scholar
19. Lin, G.Y., Lu, Y., & Yao, D.D. (2008). The stochastic knapsack revisited: switch-over policies and dynamic pricing. Operations Research 56(4): 945–957.Google Scholar
20. Lu, L.L., Chiu, S.Y., & Cox, L.A. Jr. (1999). Optimal project selection: stochastic knapsack with finite time horizon. Journal of the Operational Research Society 50(6): 645–650.Google Scholar
21. Merzifonluoğlu, Y., Geunes, J., & Romeijn, H.E. (2012). The static stochastic knapsack problem with normally distributed item sizes. Mathematical Programming 134(2): 459–489.Google Scholar
22. Morton, D.P. & Wood, R.K. (1998). On a stochastic knapsack problem and generalizations. Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search: Interfaces in Computer Science and Operations Research 9: 149–168.Google Scholar
23. Nanda, A.K. & Sengupta, D. (2005). Discrete life distributions with decreasing reversed hazard. Sankhyā: The Indian Journal of Statistics 67: 106–125.Google Scholar
24. Prekopa, A. (1973). On logarithmic concave measures and functions. Acta Scientiarum Mathematicarum (Szeged) 34: 335–343.Google Scholar
25. Ross, K.W. & Tsang, D.H.K. (1989). The stochastic knapsack problem. IEEE Transactions on Communications 37(7): 740–747.Google Scholar
26. Shaked, M. & Shanthikumar, J.G. (2007). Stochastic orders. Springer Science & Business Media.Google Scholar
27. Sniedovich, M. (1980). Preference order stochastic knapsack problems: methodological issues. Journal of the Operational Research Society 31(11): 1025–1032.Google Scholar
28. Steinberg, E. & Parks, M.S. (1979). A preference order dynamic program for a knapsack problem with stochastic rewards. Journal of the Operational Research Society 30(2): 141–147.Google Scholar
29. Toth, P. (1980). Dynamic programming algorithms for the zero-one knapsack problem. Computing 25(1): 29–45.Google Scholar
30. Van Slyke, R. & Young, Y. (2000). Finite horizon stochastic knapsacks with applications to yield management. Operations Research 48(1): 155–172.Google Scholar