Scandinavian Working Papers in Economics
Discussion Papers on Economics,
University of Southern Denmark, Department of Economics
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 ()
Additional contact information
Troels Martin Range: Hospital of South West Jutland and Institute of Regional Health Research: Centre of South West Jutland, Postal: University of Southern Denmark, Finsensgade 35, DK-6700 Esbjerg, Denmark
Dawid Kozlowski: Department of Industrial Economics and Technology Management, Postal: Norwegian University of Science and Technology, Alfred Getz veg 3, NO-7491 Trondheim, Norway
Niels Chr. Petersen: Department of Business and Economics, Postal: University of Southern Denmark, Campusvej 55, DK-5230 Odense M, Denmark
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
JEL-codes: C61
28 pages, July 6, 2017
Full text files
dpbe9_2017.pdf?la=da
Questions (including download problems) about the papers in this series should be directed to Astrid Holm Nielsen ()
Report other problems with accessing this service to Sune Karlsson ().
This page generated on 2024-02-05 17:13:32.