A Stochastic Knapsack Problem with Continuous Random Capacity

Abstract

Problem Statement: The problem of allocating a set of items in order to maximize the toal linear profit under uncertain capacity referred as a stochastic knapsack problem with continuous random capacity was studied theoretically and computationally. Approach: Two optimization based heuristic algorithms were proposed and developed for solving the problem and both efficiency and effectiveness are compared with the general purpose method using the Monte Carlo simulation. Results: For both the relaxed and the original problems, both algorithms with appropriate stepping size parameter were superior on average to the simulation approach in both computing time and solution quality. Conclusion: Therefore, both proposed approaches can be practical for large scale problem and can be used as a basic algorithm for a more complex nature in case of simultaneously random in both items weight and knapsack capacity.