Confidence bound heuristic for stochastic knapsack

Abstract

Our work is focused on one version of the traditional Knapsack Problem (KP), that is commonly known as “Stochastic Knapsack Problem” (SKP). The weight of each item is deterministic and the vector of values of the items is random with unknown distribution. The objective is to maximize the total value of the knapsack. We try a heuristic approach to get a near-optimal decision with estimated item values. Some variations to the problem are added, like difficulty and uncertainty to see if a good solution can be found regardless. We define the problem in two different settings: one where the error of prediction is related to the values and one where it is independent from them.