Knapsack Problems involving dimensions, demands and multiple choice constraints: generalization and transformations between formulations

In this paper we studied a set of knapsack problems involving the notion of dimensions, demands and multiple choice constraints. Specifically, we defined a new problem called the multiple demand multidimensional multiple choice knapsack problem and we showed it as a generalization of other related problems. Moreover, we presented a set of transformations between the different integer linear programs of the studied problems. Using these transformations, we showed that any algorithm able to solve the generalized problem can definitely solve its related problems. Then, we tested the new integer linear programs on different sets of benchmarks using the commercial software Cplex 9.0 . Computational results highlighted the ability of the generated formulations to produce a reasonable CPU time value compared with the original ones.