The Size Robust Multiple Knapsack Problem

Abstract

In this thesis we investigate the size robust multiple knapsack problem. The differences with the standard knapsack problem are, that there is more than one knapsack and that the knapsack sizes can decrease with a certain probability. To deal with this, we allow recovery by removing items. Our goal is to find a solution where the expected value is maximal.

We solve this problem with two decomposition approaches: The combined and separate decomposition model. We show that the speed-up for the demand robust shortest path problem for the combined model also works for the size robust multiple knapsack problem. We show that this speed-up can be adapted for the separate recovery decomposition model. Together with other algorithm optimizations this allows us to solve the LP-relaxation more than ten times faster than with the naive approach.

The separate recovery decomposition model appeared to be faster for the size robust knapsack problem. This is because the separate model has an easier pricing problem. However, when the number of knapsacks increases, the number of columns and constraints grows faster in the separate model. This indicates that the combined model could become better when we have more knapsacks. Moreover, the LP-relaxation of the combined model is stronger than the LP-relaxation of the separate model. Our experiments show that the separate model outperforms the combined model in solving the LP-relaxation. However, the combined model outperforms the separate model when we solve the ILP and have more than four knapsacks.

We also introduce two greedy approaches. The first approach removes the scenarios from the decomposition and moves them to the pricing problem while not increasing the difficulty of the pricing problem. This approach is expected to strongly decrease the solution time. The second greedy approach simplifies the pricing problem from the combined model. This gives a small decrease in the solution time, but gives a lower solution value for 10\% of the instances.