원문정보
초록
영어
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.
목차
1 Introduction
2 Preliminaries
2.1 Integer linear program
2.2 Knapsack problem constraints
2.3 Reduction, generalization and problems transformation
3 The Knapsack Problem Family involving the notion of dimen-sions, demands and sets
3.1 The knapsack problem
3.2 The multidimensional knapsack problem
3.3 The multiple demand multidimensional knapsack problem
3.4 The multiple choice knapsack problem
3.5 The multidimensional multiple choice knapsack problem
3.6 The multidimensional knapsack problems with generalized upper bound constraints
3.7 The multiple demand multidimensional multiple choice knapsack problem
3.8 Relation schema between problems
4 Transformations between Integer Linear Programs
4.1 Transformation of the GUBMKP into the MMKP
4.2 Transformation of the MKP into the MMKP
4.3 Transformation of the GUBMKP into the MKP
4.4 Transformation of the MMKP into the MDMKP
4.5 Transformation of the MCKP into the GUBMKP
4.6 Algorithms of MDMMKP are able to solve the other problems
5 Experimental results
5.1 Instances details
5.2 Evaluation of the transformation
6 Conclusion and future research direction
References