关键词: 多维多选择背包问题, 核, 分支定界, 整数线性规划, 组合优化

Abstract: The core has been used to design efficient algorithms for the knapsack problem. Several methods were put forward to obtain a core for Multidimensional Mutiple-choice Knapsack Problem (MMKP) as there is no algorithm based on core now. The method of obtaining a core of the Knapsack Problem (KP) was discussed firstly, and then the base solution and ordering relations of MMKP were explained in detail according to the metrics set beforehand. After that, the core which can be called subspace was obtained by three methods. The firrst method was based on the observation that which of E[lc] and E[d∞] was smaller. The second method was based on the observation that the Manhattan distance of the base solution was not too far from the optimal solution. In the third method, a total ordering was defined among all items and the first k items were taken as the core.The comparative study shows that the performance of the first one is superior on both accuracy and enumeration time. The MMKP can be solved efficiently with this method.

Key words: Multidimensional Mutiple-choice Knapsack Problem (MMKP), core, branch-and-bound, integer linear programming, combinatorial optimization