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.
Keywords: Heuristic; Knapsack; Lagrangian relaxation; Optimality.
Mhand Hifi and Lei Wu
Benchmark instances:
download (I1-13 and INST01-20)
19852total visits.