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

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.

多需求多维背包问题（MDMKP）是0 - 1背包问题的一种推广，它在理论上（NP难）和实践中都难以解决。由于其相互冲突的背包约束和需求约束，解决MDMKP可能很困难。近似解法无法保证解的质量。最近，通过使用分类树，根据在标准PC上使用CPLEX®软件包的整数规划选项的预期性能，将MDMKP分为三大类：A类——相对容易解决，B类——有些难以解决，C类——难以解决。然而，这些类别并没有相关的解决方法。本文的主要贡献在于，它针对每个类别进行了演示，说明通用整数规划软件（此处为CPLEX）如何能够迭代使用，以便有效地为MDMKP生成有界解。具体而言，简单顺序递增容差（SSIT）方法将迭代使用具有放宽容差的CPLEX，以有效地生成这些有界解。这种方法的真正优势在于，SSIT方法是根据所求解的MDMKP实例的特定类别（A、B或C）定制的。这种方法对于实践者来说很容易使用，因为它不需要耗时地编写特定问题的算法。统计分析将在执行时间和解的质量方面，将SSIT结果与CPLEX的单次执行进行比较。