Solving the multiscenario max-MIN knapsack problem exactly with column generation and branch-and-bound (Q1665694): Difference between revisions
From MaRDI portal
Latest revision as of 11:50, 16 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Solving the multiscenario max-MIN knapsack problem exactly with column generation and branch-and-bound |
scientific article |
Statements
Solving the multiscenario max-MIN knapsack problem exactly with column generation and branch-and-bound (English)
0 references
27 August 2018
0 references
Summary: Despite other variants of the standard knapsack problem, very few solution approaches have been devised for the multiscenario max-min knapsack problem. The problem consists in finding the subset of items whose total profit is maximized under the worst possible scenario. In this paper, we describe an exact solution method based on column generation and branch-and-bound for this problem. Our approach relies on a reformulation of the standard compact integer programming model based on the Dantzig-Wolfe decomposition principle. The resulting model is potentially stronger than the original one since the corresponding pricing subproblem does not have the integrality property. The details of the reformulation are presented and analysed together with those concerning the column generation and branch-and-bound procedures. To evaluate the performance of our algorithm, we conducted extensive computational experiments on large scale benchmark instances, and we compared our results with other state-of-the-art approaches under similar circumstances. We focused in particular on different relevant aspects that allow 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 the literature.
0 references
0 references
0 references
0 references
0 references
0 references