Generating bounded solutions for multi-demand multidimensional knapsack problems: a guide for operations research practitioners

Abstract

A generalization of the 0-1 knapsack problem that is hard-to-solve both theoretically (NP-hard) and in practice is the multi-demand multidimensional knapsack problem (MDMKP). Solving an MDMKP can be difficult because of its conflicting knapsack and demand constraints. Approximate solution approaches provide no guarantees on solution quality. Recently, with the use of classification trees, MDMKPs were partitioned into three general categories based on their expected performance using the integer programming option of the CPLEX^® software package on a standard PC: Category A—relatively easy to solve, Category B—somewhat difficult to solve, and Category C—difficult to solve. However, no solution methods were associated with these categories. The primary contribution of this article is that it demonstrates, customized to each category, how general-purpose integer programming software (CPLEX in this case) can be iteratively used to efficiently generate bounded solutions for MDMKPs. Specifically, the simple sequential increasing tolerance (SSIT) methodology will iteratively use CPLEX with loosening tolerances to efficiently generate these bounded solutions. The real strength of this approach is that the SSIT methodology is customized based on the particular category (A, B, or C) of the MDMKP instance being solved. This methodology is easy for practitioners to use because it requires no time-consuming effort of coding problem specific-algorithms. Statistical analyses will compare the SSIT results to a single-pass execution of CPLEX in terms of execution time and solution quality.