A Stochastic Knapsack Problem with Continuous Random Capacity
Suwitchporn Witchakul, Prapaisri Sudas Na Ayudhaya and Peerayuth Charnsethikul
DOI : 10.3844/jmssp.2008.269.276
Journal of Mathematics and Statistics
Volume 4, Issue 4
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.
© 2008 Suwitchporn Witchakul, Prapaisri Sudas Na Ayudhaya and Peerayuth Charnsethikul. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.