期刊名称：International Journal of Combinatorial Optimization Problems and Informatics
印刷版ISSN：2007-1558
电子版ISSN：2007-1558
出版年度：2012
卷号：3
期号：3
页码：43-58
语种：English
出版社：International Journal of Combinatorial Optimization Problems and Informatics
其他摘要：The Multiple-choice Multi-dimensional Knapsack Problem (MMKP) is a problem which can be encountered in real-world applications, such as service level agreement, model of allocation resources, or as a dynamic adaptation of system of resources for multimedia multi-sessions. In this paper, we investigate the use of a new model-based Lagrangian relaxation for optimally solving the MMKP. In order to tackle large-scale problem instances, we curtail the search process for providing approximate solutions. We then apply the Cplex solver using both original and equivalent models. In this case, the Cplex solver becomes more efficient when the new model is used. Also, when the proposed method is considered as a heuristic, then it outperforms the Cplex solver using the original model: new solution values are obtained.
