Scandinavian Working Papers in Economics
HomeAboutSeriesSubject/JEL codesAdvanced Search
Department of Business and Economics, University of Southern Denmark Discussion Papers of Business and Economics
Department of Business and Economics, University of Southern Denmark

No 9/2017:
A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs

Troels Martin Range (), Dawid Kozlowski and Niels Chr. Petersen ()

Abstract: 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. We combine the formulation of the SKP with a probabilistic capacity constraint (CKP) and the SKP with simple recourse (SRKP). Capacity is made an integral part of the constraint set in terms of a chance constraint as in the CKP. The chance constraint allows for a violation of capacity, but the probability of a violation beyond an imposed limit is constrained. 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 Constraint (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.

Keywords: Stochastic knapsack problem; dynamic programming; shortest path problem with resource constraints; (follow links to similar papers)

JEL-Codes: C61; (follow links to similar papers)

28 pages, July 6, 2017

Before downloading any of the electronic versions below you should read our statement on copyright.
Download GhostScript for viewing Postscript files and the Acrobat Reader for viewing and printing pdf files.

Full text versions of the paper:

dpbe9_2017.pdf?la=da    PDF-file
Download Statistics

Questions (including download problems) about the papers in this series should be directed to Lene Holbęk ()
Report other problems with accessing this service to Sune Karlsson () or Helena Lundin ().

Programing by
Design by Joachim Ekebom

Handle: RePEc:hhs:sdueko:2017_009 This page was generated on 2017-07-06 09:13:54