The linear multiple choice knapsack problem (Q1825130)

The multiple choice knapsack problem is a knapsack problem with additional multiple choice constraints. Because it is generally solved by branch-and-bound, an efficient solution technique for its linear programming relaxation is essential. This paper presents such a solution algorithm which has two important features compared with current methods: (1) it is a dual-type method which makes it easy to restart with a modified right-hand side and (2) it is faster than the Dudzinski-Walukiewicz algorithm. The algorithm proceeds by systematically perturbing the right-hand side and using a dual simplex pivot after each perturbation. The complexity is empirically found to be O(k), where k is the total number of variables, and the computation time is 2 to 3 times lower than the convex-dominance step of the Dudzinski-Walukiewicz algorithm.