A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs

Troels Martin Range*, Dawid Kozlowski, Niels Chr Petersen

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

46 Downloads (Pure)


The knapsack problem (KP) is concerned with the selection of a subset of multiple items with known positive values and weights such that the total value of selected items is maximized and their total weight does not exceed capacity. Item values, item weights, and capacity are known in the deterministic case. We consider the stochastic KP (SKP) with stochastic item weights. For this variant of the SKP we combine the chance constrained KP (CCKP) and the SKP with simple recourse (SRKP). The chance constraint allows for a violation of capacity, but the probability of a violation beyond an imposed limit is constrained. The violation of the capacity constraint is also included in the objective function in terms of a penalty function as in the SRKP. Penalty is an increasing function of the expected number of units of violation with proportionality as a special case. We formulate the SKP as a network problem and demonstrate that it can be solved by a label-setting dynamic programming approach for the shortest path problem with resource constraints (SPPRC). We develop a dominance criterion for an elimination of states in the dynamic programming approach using only the deterministic value of items along with mean and variance of the stochastic weight of items corresponding to the associated paths in the underlying network. It is shown that a lower bound for the impact of potential extensions of paths is available as an additional means to limit the number of states provided the penalty cost of expected overtime is convex. Our findings are documented in terms of a computational study.

Original languageEnglish
JournalComputers and Operations Research
Pages (from-to)111-124
Publication statusPublished - 2018


  • Dynamic programming
  • Shortest path problem with resource constraints
  • Stochastic Knapsack problem


Dive into the research topics of 'A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs'. Together they form a unique fingerprint.

Cite this