article · Probability in the Engineering and Informational Sciences · 2015

STATIC STOCHASTIC KNAPSACK PROBLEMS

Cited by 5Abstract and details only

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.

Cite this paper

APA 7

Chen, K., & Ross, S. M. (2015). STATIC STOCHASTIC KNAPSACK PROBLEMS. Probability in the Engineering and Informational Sciences, 29(4), 527–546. https://doi.org/10.1017/s0269964815000170

MLA 9

Chen, Kai, and Sheldon M. Ross. “STATIC STOCHASTIC KNAPSACK PROBLEMS.” Probability in the Engineering and Informational Sciences, vol. 29, no. 4, 2015, pp. 527–46, https://doi.org/10.1017/s0269964815000170.

Chicago

Chen, Kai, and Sheldon M. Ross. 2015. “STATIC STOCHASTIC KNAPSACK PROBLEMS.” Probability in the Engineering and Informational Sciences 29 (4): 527–46. https://doi.org/10.1017/s0269964815000170.

Harvard

Chen, K. and Ross, S.M. (2015) ‘STATIC STOCHASTIC KNAPSACK PROBLEMS’, Probability in the Engineering and Informational Sciences, 29(4), pp. 527–546. Available at: https://doi.org/10.1017/s0269964815000170.

BibTeX

@article{chen2015static,
  title = {{STATIC STOCHASTIC KNAPSACK PROBLEMS}},
  author = {Chen, Kai and Ross, Sheldon M.},
  journal = {Probability in the Engineering and Informational Sciences},
  volume = {29},
  number = {4},
  pages = {527--546},
  year = {2015},
  doi = {10.1017/s0269964815000170}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.