Solving the Multiscenario Max-Min Knapsack Problem Exactly with Column Generation and Branch-and-Bound

摘要

Despite other variants of the standard knapsack problem, very few solution approaches have beendevised for the multiscenario max-min knapsack problem. The problem consists in finding the subsetof items whose total profit is maximized under the worst possible scenario. In this paper, we describean exact solution method based on column generation and branch-and-bound for this problem. Ourapproach relies on a reformulation of the standard compact integer programming model based on theDantzig-Wolfe decomposition principle. The resulting model is potentially stronger than the originalone since the corresponding pricing subproblem does not have the integrality property. The details ofthe reformulation are presented and analysed together with those concerning the column generationand branch-and-bound procedures. To evaluate the performance of our algorithm, we conducted extensive computational experimentson large scale benchmark instances, and we compared our results with other state-of-the-artapproaches under similar circumstances. We focused in particular on different relevant aspects thatallow an objective evaluation of the efficacy of our approach. From different standpoints, the branch-and-price algorithm proved to outperform the other state-of-the-art methods described so far in theliterature.